Submission #420849


Source Code Expand

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <limits>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <complex>

using namespace std;

#define INF (INT_MAX/3)
#define PI (2*acos(0.0))
#define EPS (1e-8)

typedef long long ll;
typedef unsigned long long ull;

int par[100000];
int rnk[100000];
int N, Q, P, A, B;

void init(int n){
  for(int i = 0; i < n; i++){
    par[i] = i;
    rnk[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(rnk[x] < rnk[y]) par[x] = y;
  else{
    par[y] = x;
    if(rnk[x] == rnk[y]) rnk[x]++;
  }
}

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

int main(){
  ios_base::sync_with_stdio(0);
  cin >> N >> Q;
  init(N);
  for(int i = 0; i < Q; i++){
    cin >> P >> A >> B;
    switch(P){
      case 0:
        unite(A, B);
        break;
      case 1:
        if(same(A, B)) cout << "Yes" << endl;
        else cout << "No" << endl;
        break;
      default:
        break;
    }
  }
  return 0;
}

Submission Info

Submission Time
Task B - Union Find
User d2verb
Language C++ (GCC 4.9.2)
Score 100
Code Size 1368 Byte
Status AC
Exec Time 620 ms
Memory 1696 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 19
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 28 ms 788 KB
subtask_01_01.txt AC 408 ms 924 KB
subtask_01_02.txt AC 27 ms 1568 KB
subtask_01_03.txt AC 531 ms 920 KB
subtask_01_04.txt AC 549 ms 1692 KB
subtask_01_05.txt AC 60 ms 728 KB
subtask_01_06.txt AC 52 ms 1572 KB
subtask_01_07.txt AC 527 ms 916 KB
subtask_01_08.txt AC 587 ms 1568 KB
subtask_01_09.txt AC 25 ms 924 KB
subtask_01_10.txt AC 28 ms 1576 KB
subtask_01_11.txt AC 620 ms 804 KB
subtask_01_12.txt AC 596 ms 1680 KB
subtask_01_13.txt AC 516 ms 924 KB
subtask_01_14.txt AC 29 ms 1572 KB
subtask_01_15.txt AC 610 ms 932 KB
subtask_01_16.txt AC 539 ms 1688 KB
subtask_01_17.txt AC 400 ms 1692 KB
subtask_01_18.txt AC 409 ms 1696 KB