This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
#define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind" #include <vector> #include <iostream> #include <stack> #include <array> using namespace std; #include "../../lib/00-util/FastIO.cpp" #include "../../lib/41-union-find-tree/UndoUnionFindTree.cpp" int main() { cin.tie(0);ios::sync_with_stdio(false); int N,Q; read(N), read(Q); vector<int> t(Q+1),k(Q+1),u(Q+1),v(Q+1); for(int i=1;i<=Q;++i) { read(t[i]), read(k[i]), read(u[i]), read(v[i]); k[i]++; } vector<vector<int>> edge(Q+1); vector<vector<int>> query(Q+1); vector<int> ans(Q+1,-1); UndoUnionFindTree uf(N); for(int i=1;i<=Q;++i) { if(t[i]==0) { edge[k[i]].push_back(i); } if(t[i]==1) { query[k[i]].push_back(i); } } auto dfs = [&](auto dfs, int pa) -> void { for(int i: query[pa]) { ans[i] = uf.connected(u[i],v[i]); } for(int i: edge[pa]) { uf.merge(u[i],v[i]); dfs(dfs,i); uf.undo(); } }; dfs(dfs,0); for(int i=1;i<=Q;++i) { if(ans[i]!=-1) cout << ans[i] << "\n"; } return 0; }
#line 1 "test/union-find-tree/UndoUnionFindTree.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/persistent_unionfind" #include <vector> #include <iostream> #include <stack> #include <array> using namespace std; #line 1 "lib/00-util/FastIO.cpp" /* * @title FastIO * @docs md/util/FastIO.md */ class FastIO{ private: inline static constexpr int ch_0='0'; inline static constexpr int ch_9='9'; inline static constexpr int ch_n='-'; inline static constexpr int ch_s=' '; inline static constexpr int ch_l='\n'; inline static void endline_skip(char& ch) { while(ch==ch_l) ch=getchar(); } template<typename T> inline static void read_integer(T &x) { int neg=0; char ch; x=0; ch=getchar(); endline_skip(ch); if(ch==ch_n) neg=1,ch=getchar(); for(;(ch_0 <= ch && ch <= ch_9); ch = getchar()) x = x*10 + (ch-ch_0); if(neg) x*=-1; } template<typename T> inline static void read_unsigned_integer(T &x) { char ch; x=0; ch=getchar(); endline_skip(ch); for(;(ch_0 <= ch && ch <= ch_9); ch = getchar()) x = x*10 + (ch-ch_0); } inline static void read_string(string &x) { char ch; x=""; ch=getchar(); endline_skip(ch); for(;(ch != ch_s && ch!=ch_l); ch = getchar()) x.push_back(ch); } inline static char ar[40]; inline static char *ch_ar; template<typename T> inline static void write_integer(T x) { ch_ar=ar; if(x< 0) putchar(ch_n), x=-x; if(x==0) putchar(ch_0); for(;x;x/=10) *ch_ar++=(ch_0+x%10); while(ch_ar--!=ar) putchar(*ch_ar); } public: inline static void read(int &x) {read_integer<int>(x);} inline static void read(long long &x) {read_integer<long long>(x);} inline static void read(unsigned int &x) {read_unsigned_integer<unsigned int>(x);} inline static void read(unsigned long long &x) {read_unsigned_integer<unsigned long long>(x);} inline static void read(string &x) {read_string(x);} inline static void read(__int128_t &x) {read_integer<__int128_t>(x);} inline static void write(__int128_t x) {write_integer<__int128_t>(x);} inline static void write(char x) {putchar(x);} }; #define read(arg) FastIO::read(arg) #define write(arg) FastIO::write(arg) #line 1 "lib/41-union-find-tree/UndoUnionFindTree.cpp" /* * @title UndoUnionFindTree - Undoつき Union Find Tree * @docs md/union-find-tree/UndoUnionFindTree.md */ class UndoUnionFindTree { vector<int> parent; stack<array<int,2>> history; inline int root(int n) { return (parent[n]<0?n:root(parent[n])); } public: UndoUnionFindTree(const int N = 1) : parent(N,-1){ } inline bool connected(const int n, const int m) { return root(n) == root(m); } inline void merge(int n,int m) { n = root(n); m = root(m); history.push({n,parent[n]}); history.push({m,parent[m]}); if (n == m) return; if(parent[n]>parent[m]) swap(n, m); parent[n] += parent[m]; parent[m] = n; } inline int size(const int n){ return (-parent[root(n)]); } inline int operator[](const int n) { return root(n); } inline void print() { for(int i = 0; i < parent.size(); ++i) cout << root(i) << " "; cout << endl; } inline void undo() { for(int i=0;i<2;++i) { auto ar=history.top(); history.pop(); parent[ar[0]]=ar[1]; } } }; #line 10 "test/union-find-tree/UndoUnionFindTree.test.cpp" int main() { cin.tie(0);ios::sync_with_stdio(false); int N,Q; read(N), read(Q); vector<int> t(Q+1),k(Q+1),u(Q+1),v(Q+1); for(int i=1;i<=Q;++i) { read(t[i]), read(k[i]), read(u[i]), read(v[i]); k[i]++; } vector<vector<int>> edge(Q+1); vector<vector<int>> query(Q+1); vector<int> ans(Q+1,-1); UndoUnionFindTree uf(N); for(int i=1;i<=Q;++i) { if(t[i]==0) { edge[k[i]].push_back(i); } if(t[i]==1) { query[k[i]].push_back(i); } } auto dfs = [&](auto dfs, int pa) -> void { for(int i: query[pa]) { ans[i] = uf.connected(u[i],v[i]); } for(int i: edge[pa]) { uf.merge(u[i],v[i]); dfs(dfs,i); uf.undo(); } }; dfs(dfs,0); for(int i=1;i<=Q;++i) { if(ans[i]!=-1) cout << ans[i] << "\n"; } return 0; }