CODE FESTIVAL 2016 Final

Submission #992602

Source codeソースコード

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

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF = 1e9;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

const int MAX_N = 1e5;
class UnionFind {
private:
    int rank[MAX_N];

public:
    int par[MAX_N];
    
    void init(int n)
    {
        for (int i=0; i<n; i++) {
            par[i]=i;
            rank[i]=0;
        }
    }
    
    // 木の根を求める
    int find(int x)
    {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }
    
    // xとyの属する集合を併合する
    void merge(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]++;
        }
    }
    
    // xとyが同じ集合に属するか判定する
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
};

const int MAX_M = 1e5;
set<int> can[MAX_M];

int main()
{
    ios::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;
    rep(i, N) {
        int K; cin >> K;
        rep(j, K) {
            int L;
            cin >> L;
            L--;
            can[L].insert(i);
        }
    }

    UnionFind UF;
    UF.init(N);

    rep(i, M) {
        if (can[i].size() == 0) continue;
        for (auto u : can[i]) {
            UF.merge(i, u);
        }
    }

    bool ok = true;
    rep(i, N) {
        if (!UF.same(i, 0)) ok = false;
    }
    cout << (ok ? "YES" : "NO") << endl;
}

Submission

Task問題 C - Interpretation
User nameユーザ名 OUDON
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 2023 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 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
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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 7 ms 4992 KB
01-02.txt AC 7 ms 4992 KB
01-03.txt AC 7 ms 4992 KB
01-04.txt AC 7 ms 4992 KB
01-05.txt WA
01-06.txt AC 7 ms 4992 KB
01-07.txt AC 7 ms 4992 KB
01-08.txt WA
01-09.txt AC 7 ms 4992 KB
01-10.txt AC 7 ms 4992 KB
02-01.txt RE
02-02.txt WA
02-03.txt WA
02-04.txt RE
02-05.txt AC 42 ms 10240 KB
02-06.txt RE
02-07.txt AC 43 ms 10368 KB
02-08.txt WA
02-09.txt AC 47 ms 10368 KB
02-10.txt AC 32 ms 9984 KB
02-11.txt WA
02-12.txt AC 32 ms 9856 KB
02-13.txt WA
sample-01.txt AC 7 ms 4992 KB
sample-02.txt AC 7 ms 4992 KB