Submission #2214698


Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ROF(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
#define SUM(a) accumulate(all(a),0)
#define pb push_back
#define fst first
#define snd second
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef long long ll;

struct UnionFind {
  vector<int> par, rank;

  UnionFind(int size){
    par.resize(size);
    rank.resize(size);
    rep(i,size){
      par[i] = i;
      //rank[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(rank[x] < rank[y]){
      par[x] = y;
    }else{
      par[y] = x;
      if(rank[x] == rank[y]) rank[x]++;
    }
  }

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

  void print(){
    cout << "i :\t";
    rep(i, par.size()) cout << i << "\t";
    cout << endl;
    cout << "par :\t";
    rep(i, par.size()) cout << par[i] << "\t";
    cout << endl;
    cout << "rank :\t";
    rep(i, par.size()) cout << rank[i] << "\t";
    cout << endl;
  }
};

main(){
  int n,k,l; cin >> n >> k >> l;
  
  struct UnionFind a(n), b(n);

  rep(i,k){
    int p,q; cin >> p >> q;
    a.unite(p-1,q-1);
  }

  rep(i,l){
    int r,s; cin >> r >> s;
    b.unite(r-1,s-1);
  }
  
  //a.print();
  //b.print();

  map<pii,int> mp;
  rep(i,n){
    mp[pii(a.par[i],b.par[i])]++;
  }

  rep(i,n){
    cout << mp[pii(a.par[i],b.par[i])];
    if(i == n-1) cout << endl;
    else cout << " ";
  }
}

Submission Info

Submission Time
Task D - Connectivity
User kimitsu_emt
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1912 Byte
Status WA
Exec Time 211 ms
Memory 15104 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 6
WA × 12
Set Name Test Cases
Sample subtask0_0.txt, subtask0_1.txt, subtask0_2.txt
All subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
subtask0_0.txt AC 1 ms 256 KB
subtask0_1.txt AC 1 ms 256 KB
subtask0_2.txt AC 1 ms 256 KB
subtask1_0.txt AC 83 ms 256 KB
subtask1_1.txt WA 211 ms 15104 KB
subtask1_10.txt AC 88 ms 256 KB
subtask1_11.txt WA 198 ms 13440 KB
subtask1_12.txt WA 144 ms 12928 KB
subtask1_13.txt WA 155 ms 14208 KB
subtask1_14.txt WA 164 ms 11136 KB
subtask1_2.txt WA 127 ms 9856 KB
subtask1_3.txt WA 162 ms 14080 KB
subtask1_4.txt WA 167 ms 11904 KB
subtask1_5.txt AC 89 ms 256 KB
subtask1_6.txt WA 187 ms 12672 KB
subtask1_7.txt WA 145 ms 14208 KB
subtask1_8.txt WA 168 ms 14336 KB
subtask1_9.txt WA 156 ms 8704 KB