Submission #7473647


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;
int n, q;
int p[MAX_Q], a[MAX_Q], b[MAX_Q];
int par[MAX_N];
int depth[MAX_N];

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

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

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]++;
  }
}

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) {
    if (p[i] == 0) unite(a[i], b[i]);
    else {
      if (same(a[i], b[i])) 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 100
Code Size 904 Byte
Status
Exec Time 479 ms
Memory 3968 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_sample_01.txt
All 100 / 100 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 275 ms 2176 KB
subtask_01_02.txt 1 ms 1024 KB
subtask_01_03.txt 420 ms 3328 KB
subtask_01_04.txt 475 ms 3968 KB
subtask_01_05.txt 24 ms 512 KB
subtask_01_06.txt 27 ms 1280 KB
subtask_01_07.txt 432 ms 3200 KB
subtask_01_08.txt 475 ms 3968 KB
subtask_01_09.txt 1 ms 256 KB
subtask_01_10.txt 2 ms 1024 KB
subtask_01_11.txt 406 ms 3200 KB
subtask_01_12.txt 474 ms 3968 KB
subtask_01_13.txt 361 ms 2560 KB
subtask_01_14.txt 3 ms 1024 KB
subtask_01_15.txt 431 ms 3200 KB
subtask_01_16.txt 479 ms 3968 KB
subtask_01_17.txt 334 ms 3712 KB
subtask_01_18.txt 330 ms 3712 KB