CODE FESTIVAL 2016 Final

Submission #1757018

Source codeソースコード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <set>
#include <cmath>
#include <map>
#include <cstring>
#include <stack>
#include <cstdio>
#include <complex>
#include <iomanip>
#include <cctype>
#include <cassert>
#include <numeric>
#include <climits>
#include <deque>
#include <random>
#include <functional>
#include <unordered_map>
#define rep(i,n) for(int i=0;i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define show(x) cout << #x << " = " << x << endl;
#define MAX_N 100005
int par[MAX_N];
int ran[MAX_N];

void init(int n){
    rep(i,n){
        par[i] = i;
        ran[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(ran[x] < ran[y]){
        par[x] = y;
    }else{
        par[y] = x;
        if(ran[x] == ran[y]) ran[x]++;
    }
}

bool same(int x, int y){
    return find(x) == find(y);
}
vector<int>g[10005];
int main(){
    int n,m;
    cin >> n >> m;
    int k;
    init(n);
    rep(i,n){
        cin >> k;
        int l;
        rep(j,k){
            cin >> l;
            l--;
            g[l].push_back(i);
        }
    }
    rep(i,m){
        if(g[i].size()>=2)rep(j,g[i].size()-1){
            //cout << g[i][j] << " ";
            //cout << g[i][j] << " "<< g[i][j+1] << endl;
            unite(g[i][j],g[i][j+1]);
        }
        //cout << endl;
    }
    int same = find(0);
    rep(i,n){
        if(same != find(i)){
            cout <<"NO" << endl;
            return 0;
        }
    }
    cout <<"YES" << endl;
}

Submission

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

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 0 / 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 512 KB
01-02.txt AC 2 ms 512 KB
01-03.txt AC 2 ms 512 KB
01-04.txt AC 2 ms 512 KB
01-05.txt AC 2 ms 512 KB
01-06.txt AC 2 ms 512 KB
01-07.txt AC 2 ms 512 KB
01-08.txt AC 2 ms 512 KB
01-09.txt AC 2 ms 512 KB
01-10.txt AC 2 ms 512 KB
02-01.txt RE
02-02.txt AC 47 ms 1792 KB
02-03.txt RE
02-04.txt RE
02-05.txt AC 53 ms 1920 KB
02-06.txt RE
02-07.txt AC 54 ms 1920 KB
02-08.txt AC 37 ms 1792 KB
02-09.txt RE
02-10.txt RE
02-11.txt RE
02-12.txt RE
02-13.txt RE
sample-01.txt AC 1 ms 512 KB
sample-02.txt AC 1 ms 512 KB