AtCoder Typical Contest 001

Submission #7138343

Source codeソースコード

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

// UnionFind
struct UnionFind{
  VI par,sizes; // par[i]:iの親の番号
  UnionFind(int n) : par(n), sizes(n,1){ // 最初は全てが根であるとして初期化
    rep(i,n) par[i] = i;
  }
  int root(int x){
    if(par[x]==x) return x;
    return par[x] = root(par[x]);
  }
  void unite(int x, int y){
    int rx = root(x); int ry = root(y);
    if(rx==ry) return;
    if(sizes[rx]<sizes[ry]) swap(rx,ry);
    par[ry] = rx;
    sizes[rx] += sizes[ry];
  }
  bool same(int x, int y){
    return root(x)==root(y);
  }
  int size(int x){
    return sizes[root(x)];
  }
};

signed main(){
  int n,q; cin>>n>>q;
  UnionFind tree(n);
  rep(i,q){
    int p,a,b; cin>>p>>a>>b; a--; b--;
    if(p){
      if(tree.same(a,b)) cout << "Yes" << endl;
      else cout << "No" << endl;
    }else{
      tree.unite(a,b);
    }
  }
  return 0;
}

Submission

Task問題 B - Union Find
User nameユーザ名 m_9719
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 2179 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 207 ms 640 KB
subtask_01_02.txt AC 2 ms 1024 KB
subtask_01_03.txt AC 338 ms 1024 KB
subtask_01_04.txt AC 340 ms 1664 KB
subtask_01_05.txt AC 20 ms 256 KB
subtask_01_06.txt AC 18 ms 1024 KB
subtask_01_07.txt WA
subtask_01_08.txt AC 348 ms 1664 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 341 ms 1664 KB
subtask_01_13.txt AC 276 ms 768 KB
subtask_01_14.txt AC 2 ms 1024 KB
subtask_01_15.txt WA
subtask_01_16.txt AC 348 ms 1664 KB
subtask_01_17.txt AC 208 ms 1408 KB
subtask_01_18.txt AC 200 ms 1408 KB