Submission #420182
Source Code Expand
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y-1);(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
struct UnionFind {
vector<int> data;
UnionFind(int size) : data(size, -1) { }
bool unionSet(int x, int y) {
x = root(x); y = root(y);
if (x != y) {
if (data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
}
return x != y;
}
bool findSet(int x, int y) {
return root(x) == root(y);
}
int root(int x) {
return data[x] < 0 ? x : data[x] = root(data[x]);
}
int size(int x) {
return -data[root(x)];
}
};
int main(){
ios_base::sync_with_stdio(false);
cout<<fixed<<setprecision(0);
int n,q,a,b,c;
cin>>n>>q;
UnionFind uf(n);
rep(i,q){
cin>>a>>b>>c;
if(a){
cout<<(uf.findSet(c,b)?"Yes":"No")<<endl;
}else{
uf.unionSet(c,b);
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Union Find |
User |
nuip |
Language |
C++11 (GCC 4.9.2) |
Score |
100 |
Code Size |
1928 Byte |
Status |
AC |
Exec Time |
584 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 |
26 ms |
916 KB |
subtask_01_01.txt |
AC |
347 ms |
924 KB |
subtask_01_02.txt |
AC |
28 ms |
1308 KB |
subtask_01_03.txt |
AC |
527 ms |
920 KB |
subtask_01_04.txt |
AC |
577 ms |
1312 KB |
subtask_01_05.txt |
AC |
53 ms |
920 KB |
subtask_01_06.txt |
AC |
56 ms |
1192 KB |
subtask_01_07.txt |
AC |
536 ms |
744 KB |
subtask_01_08.txt |
AC |
584 ms |
1192 KB |
subtask_01_09.txt |
AC |
26 ms |
800 KB |
subtask_01_10.txt |
AC |
27 ms |
1188 KB |
subtask_01_11.txt |
AC |
531 ms |
928 KB |
subtask_01_12.txt |
AC |
570 ms |
1180 KB |
subtask_01_13.txt |
AC |
426 ms |
840 KB |
subtask_01_14.txt |
AC |
28 ms |
1304 KB |
subtask_01_15.txt |
AC |
535 ms |
924 KB |
subtask_01_16.txt |
AC |
566 ms |
1188 KB |
subtask_01_17.txt |
AC |
349 ms |
1192 KB |
subtask_01_18.txt |
AC |
346 ms |
1312 KB |