Submission #420309
Source Code Expand
#include<bits/stdc++.h> using namespace std; template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; } template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " "<<a.second; } template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; } template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; } #define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++) #define ALL(v) (v).begin(), (v).end() #define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());} #define fr first #define sc second typedef pair< int , int > Pi; typedef pair< int , Pi > Pii; typedef long long int64; const int INF = 1 << 30; struct UnionFind { vector< int > data; UnionFind(int sz) { data.assign(sz, -1); } void Union(int x, int y) { x = Find(x), y = Find(y); if(x == y) return; if(data[x] < data[y]) swap(x, y); data[y] += data[x]; data[x] = y; } int Find(int x){ if(data[x] < 0) return(x); else return(data[x] = Find(data[x])); } }; int main() { int N, Q; cin >> N >> Q; UnionFind uf(N); for(int i = 0; i < Q; i++) { int P, A, B; cin >> P >> A >> B; if(P == 0) uf.Union(A, B); else if(uf.Find(A) == uf.Find(B)) puts("Yes"); else puts("No"); } return(0); }
Submission Info
Submission Time | |
---|---|
Task | B - Union Find |
User | ei13333 |
Language | C++ (GCC 4.9.2) |
Score | 100 |
Code Size | 1582 Byte |
Status | AC |
Exec Time | 958 ms |
Memory | 1312 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 | 31 ms | 716 KB |
subtask_01_01.txt | AC | 564 ms | 736 KB |
subtask_01_02.txt | AC | 28 ms | 1292 KB |
subtask_01_03.txt | AC | 747 ms | 800 KB |
subtask_01_04.txt | AC | 944 ms | 1176 KB |
subtask_01_05.txt | AC | 75 ms | 800 KB |
subtask_01_06.txt | AC | 70 ms | 1124 KB |
subtask_01_07.txt | AC | 877 ms | 920 KB |
subtask_01_08.txt | AC | 946 ms | 1188 KB |
subtask_01_09.txt | AC | 27 ms | 800 KB |
subtask_01_10.txt | AC | 27 ms | 1112 KB |
subtask_01_11.txt | AC | 630 ms | 920 KB |
subtask_01_12.txt | AC | 920 ms | 1312 KB |
subtask_01_13.txt | AC | 707 ms | 920 KB |
subtask_01_14.txt | AC | 29 ms | 1304 KB |
subtask_01_15.txt | AC | 814 ms | 800 KB |
subtask_01_16.txt | AC | 958 ms | 1184 KB |
subtask_01_17.txt | AC | 674 ms | 1304 KB |
subtask_01_18.txt | AC | 669 ms | 1308 KB |