AtCoder Typical Contest 001

Submission #7473587

Source codeソースコード

#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

Task問題 B - Union Find
User nameユーザ名 fum
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 1023 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_sample_01.txt
All 0 / 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample_01.txt AC 1 ms 256 KB
subtask_01_01.txt AC 278 ms 2048 KB
subtask_01_02.txt AC 2 ms 1024 KB
subtask_01_03.txt AC 412 ms 3328 KB
subtask_01_04.txt AC 480 ms 3968 KB
subtask_01_05.txt AC 25 ms 512 KB
subtask_01_06.txt AC 27 ms 1280 KB
subtask_01_07.txt WA
subtask_01_08.txt AC 481 ms 3968 KB
subtask_01_09.txt WA
subtask_01_10.txt AC 2 ms 1024 KB
subtask_01_11.txt WA
subtask_01_12.txt AC 484 ms 3968 KB
subtask_01_13.txt AC 364 ms 2560 KB
subtask_01_14.txt AC 3 ms 1024 KB
subtask_01_15.txt WA
subtask_01_16.txt AC 481 ms 3968 KB
subtask_01_17.txt AC 329 ms 3712 KB
subtask_01_18.txt AC 330 ms 3712 KB