Submission #6139919
Source Code Expand
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i,x) for(int i=1;i<=(int)(x);i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=(int)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
int a[3];
class UnionFind {
public:
vector<int> rank, p;
UnionFind() {}
UnionFind(int size) {
rank.resize(size, 0);
p.resize(size, 0);
for (int i = 0; i < size; ++i) {
makeSet(i);
}
}
void makeSet(int x) {
p[x] = x;
rank[x] = 0;
}
void link(int x, int y) {
if (rank[x] > rank[y]) {
p[y] = x;
} else {
p[x] = y;
if (rank[x] == rank[y]) {
++rank[x];
}
}
}
bool same(int x, int y) {
return findSet(x) == findSet(y);
}
void unite(int x, int y) {
link(findSet(x), findSet(y));
}
int findSet(int x) {
if (p[x] != x) {
p[x] = findSet(p[x]);
}
return p[x];
}
};
int main() {
int n, q, com, a, b;
cin >> n >> q;
UnionFind* ds = new UnionFind(n);
for (int i = 0; i < q; ++i) {
cin >> com >> a >> b;
if (com == 0) {
ds->unite(a, b);
}
else {
if (ds->same(a, b)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Union Find |
User |
iroha168 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2259 Byte |
Status |
AC |
Exec Time |
470 ms |
Memory |
1664 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 |
1 ms |
256 KB |
subtask_01_01.txt |
AC |
280 ms |
640 KB |
subtask_01_02.txt |
AC |
2 ms |
1024 KB |
subtask_01_03.txt |
AC |
427 ms |
1024 KB |
subtask_01_04.txt |
AC |
467 ms |
1664 KB |
subtask_01_05.txt |
AC |
25 ms |
256 KB |
subtask_01_06.txt |
AC |
26 ms |
1024 KB |
subtask_01_07.txt |
AC |
436 ms |
896 KB |
subtask_01_08.txt |
AC |
457 ms |
1664 KB |
subtask_01_09.txt |
AC |
1 ms |
256 KB |
subtask_01_10.txt |
AC |
2 ms |
1024 KB |
subtask_01_11.txt |
AC |
439 ms |
896 KB |
subtask_01_12.txt |
AC |
470 ms |
1664 KB |
subtask_01_13.txt |
AC |
355 ms |
768 KB |
subtask_01_14.txt |
AC |
3 ms |
1024 KB |
subtask_01_15.txt |
AC |
422 ms |
768 KB |
subtask_01_16.txt |
AC |
464 ms |
1664 KB |
subtask_01_17.txt |
AC |
316 ms |
1408 KB |
subtask_01_18.txt |
AC |
309 ms |
1408 KB |