Submission #2338382
Source Code Expand
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;
#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define rep(n, i) Rep(0, n-1, i)
#define MAX 200000
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef std::priority_queue<int> IntPrioQueue; //Z->A
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue; //A->Z
struct UnionFind {
//number of parents(par[i] = i => root)
vector <int> par;
//rank of tree
vector <int> rank;
UnionFind(int n) : par(n), rank(n, 1) {
//initialize
rep(n, i) par[i] = i;
}
//find root (keiroasshuku at the same time)
int root(int x){
if (par[x] == x) return x;
else return par[x] = root(par[x]);
}
//unite
void unite(int x, int y){
x = root(x);
y = root(y);
if (x == y) return;
if (rank[x] > rank[y]) swap(x, y);
par[x] = y;
if (rank[x] == rank[y]) rank[y]++;
}
//same tree?
bool same(int x, int y){
return root(x) == root(y);
}
};
/*
//number of elements
const int MAX_NODE = 100000;
//number of parents(par[i] = i => root)
int par[MAX_NODE];
//initialize
void init(int n){
rep(n, i) par[i] = i;
}
//solve root
int root(int x){
if (par[x] == x) return x;
else return par[x] = root(par[x]);
}
//unit?
bool same(int x, int y){
return root(x) == root(y);
}
//unite
void unite(int x, int y){
x = root(x);
y = root(y);
if (x == y) return;
par[x] = y;
}*/
void solve(void){
int N, Q;
cin >> N >> Q;
UnionFind uf(N);
rep(Q, meaningless){
int p, a, b;
scanf("%d %d %d\n", &p, &a, &b);
if (p == 0) uf.unite(a, b);
else if (p == 1) {
printf("%s\n", uf.same(a, b)?"Yes":"No");
}
}
}
int main(void){
solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Union Find |
User |
sifi_border |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2326 Byte |
Status |
AC |
Exec Time |
53 ms |
Memory |
1664 KB |
Compile Error
./Main.cpp: In function ‘void solve()’:
./Main.cpp:97:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d\n", &p, &a, &b);
^
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 |
31 ms |
640 KB |
subtask_01_02.txt |
AC |
2 ms |
1024 KB |
subtask_01_03.txt |
AC |
44 ms |
1024 KB |
subtask_01_04.txt |
AC |
52 ms |
1664 KB |
subtask_01_05.txt |
AC |
4 ms |
256 KB |
subtask_01_06.txt |
AC |
5 ms |
1024 KB |
subtask_01_07.txt |
AC |
48 ms |
768 KB |
subtask_01_08.txt |
AC |
53 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 |
47 ms |
896 KB |
subtask_01_12.txt |
AC |
52 ms |
1664 KB |
subtask_01_13.txt |
AC |
39 ms |
768 KB |
subtask_01_14.txt |
AC |
2 ms |
1024 KB |
subtask_01_15.txt |
AC |
47 ms |
896 KB |
subtask_01_16.txt |
AC |
53 ms |
1664 KB |
subtask_01_17.txt |
AC |
52 ms |
1408 KB |
subtask_01_18.txt |
AC |
51 ms |
1408 KB |