Submission #420182


Source Code Expand

#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y-1);(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};
int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  int n,q,a,b,c;
  cin>>n>>q;
  UnionFind uf(n);
  rep(i,q){
    cin>>a>>b>>c;
    if(a){
      cout<<(uf.findSet(c,b)?"Yes":"No")<<endl;
    }else{
      uf.unionSet(c,b);
    }
  }
  return 0;
}

Submission Info

Submission Time
Task B - Union Find
User nuip
Language C++11 (GCC 4.9.2)
Score 100
Code Size 1928 Byte
Status AC
Exec Time 584 ms
Memory 1312 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 26 ms 916 KB
subtask_01_01.txt AC 347 ms 924 KB
subtask_01_02.txt AC 28 ms 1308 KB
subtask_01_03.txt AC 527 ms 920 KB
subtask_01_04.txt AC 577 ms 1312 KB
subtask_01_05.txt AC 53 ms 920 KB
subtask_01_06.txt AC 56 ms 1192 KB
subtask_01_07.txt AC 536 ms 744 KB
subtask_01_08.txt AC 584 ms 1192 KB
subtask_01_09.txt AC 26 ms 800 KB
subtask_01_10.txt AC 27 ms 1188 KB
subtask_01_11.txt AC 531 ms 928 KB
subtask_01_12.txt AC 570 ms 1180 KB
subtask_01_13.txt AC 426 ms 840 KB
subtask_01_14.txt AC 28 ms 1304 KB
subtask_01_15.txt AC 535 ms 924 KB
subtask_01_16.txt AC 566 ms 1188 KB
subtask_01_17.txt AC 349 ms 1192 KB
subtask_01_18.txt AC 346 ms 1312 KB