Submission #420554
Source Code Expand
//union find tree #include<iostream> #include<vector> #define rep(i,j) for(int i=0;i<j;i++) using namespace std; template<typename Natural> class UnionFindTree { public: Natural Node_num; vector<Natural> parents; vector<Natural> ranks; UnionFindTree(Natural n):Node_num(n+1) { n++;//index=1_to_nに対応 parents.resize(n); ranks.resize(n); for(Natural i=0;i<n;i++) { parents[i]=i; ranks[i]=0; } } Natural get_root(Natural x) { if(parents[x]==x)return x; else { return parents[x]=get_root(parents[x]); } } void unite(Natural x,Natural y) { if( (x=get_root(x))!=(y=get_root(y)) ) { if(ranks[x]>ranks[y]) parents[y]=x; else if(ranks[x]<ranks[y]) parents[x]=y; else { parents[x]=y; ranks[y]++; } } } bool is_sameset(Natural x,Natural y) { return get_root(x)==get_root(y); } }; int main(){ int N,Q; cin>>N>>Q; UnionFindTree<int> UF(N); rep(i,Q){ int P,A,B; cin>>P>>A>>B; if(P==0){ UF.unite(A, B); } if(P==1){ cout<< (UF.is_sameset(A,B) ? "Yes" : "No") << endl; } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Union Find |
User | cormoran |
Language | C++ (GCC 4.9.2) |
Score | 100 |
Code Size | 1233 Byte |
Status | AC |
Exec Time | 1004 ms |
Memory | 1696 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt |
All | 00_sample_01.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 27 ms | 740 KB |
subtask_01_01.txt | AC | 587 ms | 928 KB |
subtask_01_02.txt | AC | 27 ms | 1576 KB |
subtask_01_03.txt | AC | 689 ms | 800 KB |
subtask_01_04.txt | AC | 1004 ms | 1572 KB |
subtask_01_05.txt | AC | 76 ms | 804 KB |
subtask_01_06.txt | AC | 78 ms | 1696 KB |
subtask_01_07.txt | AC | 899 ms | 920 KB |
subtask_01_08.txt | AC | 943 ms | 1568 KB |
subtask_01_09.txt | AC | 27 ms | 916 KB |
subtask_01_10.txt | AC | 29 ms | 1692 KB |
subtask_01_11.txt | AC | 740 ms | 920 KB |
subtask_01_12.txt | AC | 833 ms | 1692 KB |
subtask_01_13.txt | AC | 798 ms | 920 KB |
subtask_01_14.txt | AC | 33 ms | 1532 KB |
subtask_01_15.txt | AC | 734 ms | 796 KB |
subtask_01_16.txt | AC | 885 ms | 1692 KB |
subtask_01_17.txt | AC | 644 ms | 1564 KB |
subtask_01_18.txt | AC | 622 ms | 1560 KB |