CODE FESTIVAL 2016 Final

Submission #6857962

Source codeソースコード

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()

struct UnionFind {
  vector<int> par;
  vector<int> sizes;

  UnionFind(int N) : par(N), sizes(N, 1) {
    for(int i = 0; i < N; i++) par.at(i) = i;
  }

  int find(int x) { 
    if (par.at(x) == x) return x;
    return par.at(x) = find(par.at(x));
  }

  void unite(int x, int y) {
    int rx = find(x); 
    int ry = find(y); 
    if (rx == ry) return; 
    if (sizes.at(rx) < sizes.at(ry)) swap(rx,ry);
    par.at(ry) = rx;
    sizes.at(rx) += sizes.at(ry);    
  }

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

  int size(int x){
    return sizes.at(find(x));
  }

  int num_of_connected_components(){
    int ret = 0;
    for(int i = 0; i < par.size(); i++){
      if(find(i) == i) ret++;
    }
    return ret;
  }
};

int main(){
  ll n,m; cin >> n >> m;
  UnionFind uft(n);
  vector<vector<ll>> lang(m);
  REP(i,n){
    ll k; cin >> k;
    REP(j,k){
      ll l; cin >> l;
      l--;
      lang[l].push_back(i);
    }
  }
  REP(i,m){
    ll s = lang[i].size();
    if(s<2) continue;
    FOR(j,1,s){
      uft.unite(lang[i][0], lang[i][j]);
    }
  }
  if(uft.num_of_connected_components()==1) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Submission

Task問題 C - Interpretation
User nameユーザ名 batsumaru
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 400
Source lengthソースコード長 1610 Byte
File nameファイル名
Exec time実行時間 50 ms
Memory usageメモリ使用量 4736 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
dataset1 200 / 200 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt
dataset2 200 / 200 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,02-01.txt,02-02.txt,02-03.txt,02-04.txt,02-05.txt,02-06.txt,02-07.txt,02-08.txt,02-09.txt,02-10.txt,02-11.txt,02-12.txt,02-13.txt,sample-01.txt,sample-02.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 2 ms 256 KB
01-04.txt AC 1 ms 256 KB
01-05.txt AC 2 ms 256 KB
01-06.txt AC 1 ms 256 KB
01-07.txt AC 1 ms 256 KB
01-08.txt AC 1 ms 256 KB
01-09.txt AC 1 ms 256 KB
01-10.txt AC 1 ms 256 KB
02-01.txt AC 40 ms 4736 KB
02-02.txt AC 42 ms 2176 KB
02-03.txt AC 40 ms 3200 KB
02-04.txt AC 50 ms 4736 KB
02-05.txt AC 46 ms 2560 KB
02-06.txt AC 48 ms 4736 KB
02-07.txt AC 48 ms 2560 KB
02-08.txt AC 34 ms 1992 KB
02-09.txt AC 48 ms 4472 KB
02-10.txt AC 41 ms 3836 KB
02-11.txt AC 41 ms 3836 KB
02-12.txt AC 42 ms 3840 KB
02-13.txt AC 40 ms 3712 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB