Submission #7473587


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

const int MAX_Q = 200005;
const int MAX_N = 100005;

//input
int n, q;
int p[MAX_Q], a[MAX_Q], b[MAX_Q];

/*union-find*/
int par[MAX_N];
int depth[MAX_N];

//Initilize
void init(int n) {
  rep(i, n) par[i] = i;
  rep(i ,n) depth[i] = 0;
}

//search root
int find(int x) {
  if (par[x] == x) return x;
  else return par[x] = find(par[x]);
}

//unite x to y
void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return ;
  if (depth[x] < depth[y]) par[x] = y;
  else {
    par[y] = x;
    if (depth[x] == depth[y]) depth[x]++;
  }
}

//check
bool same(int x, int y) {
  return find(x) == find(y);
}

int main() {
  cin>>n>>q;
  rep(i, q) cin >>p[i]>>a[i]>>b[i];
  init(n);
  rep(i, q) {
    int x = a[i] - 1;
    int y = b[i] - 1;
    if (p[i] == 0) unite(x, y);
    else {
      if (same(x, y)) cout<<"Yes"<<endl;
      else cout<<"No"<<endl;
    }
  }
}

Submission Info

Submission Time
Task B - Union Find
User fuminiton
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1023 Byte
Status
Exec Time 484 ms
Memory 3968 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
× 1
× 15
× 4
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 1 ms 256 KB
subtask_01_01.txt 278 ms 2048 KB
subtask_01_02.txt 2 ms 1024 KB
subtask_01_03.txt 412 ms 3328 KB
subtask_01_04.txt 480 ms 3968 KB
subtask_01_05.txt 25 ms 512 KB
subtask_01_06.txt 27 ms 1280 KB
subtask_01_07.txt 438 ms 3200 KB
subtask_01_08.txt 481 ms 3968 KB
subtask_01_09.txt 1 ms 256 KB
subtask_01_10.txt 2 ms 1024 KB
subtask_01_11.txt 409 ms 3200 KB
subtask_01_12.txt 484 ms 3968 KB
subtask_01_13.txt 364 ms 2560 KB
subtask_01_14.txt 3 ms 1024 KB
subtask_01_15.txt 426 ms 3200 KB
subtask_01_16.txt 481 ms 3968 KB
subtask_01_17.txt 329 ms 3712 KB
subtask_01_18.txt 330 ms 3712 KB