Submission #5693537


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<ll, ll> P;
//unionfind
const int MAX_N = 100010;
ll m, n;
int par[MAX_N];    //親
int deapth[MAX_N]; //木の深さ
int cnt[MAX_N];
ll num;

//n要素で初期化
void init(int n)
{
    for (int i = 0; i < n; i++)
    {
        par[i] = i;
        deapth[i] = 0;
        cnt[i] = 1;
    }
}
//木の根を求める
int find(int x)
{
    if (par[x] == x)
    {
        return x;
    }
    else
    {
        return par[x] = find(par[x]);
    }
}

//xとyの属する集合を併合
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
        return;
    if (deapth[x] < deapth[y])
    {
        par[x] = y;
        cnt[y] += cnt[x];
    }
    else
    {
        par[y] = x;
        cnt[x] += cnt[y];
        if (deapth[x] == deapth[y])
            deapth[x]++;
    }
}

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

Submission Info

Submission Time
Task C - Interpretation
User octo
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1628 Byte
Status AC
Exec Time 47 ms
Memory 1792 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 200 / 200
Status
AC × 2
AC × 12
AC × 27
Set Name Test Cases
sample sample-01.txt, sample-02.txt
dataset1 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 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
Case Name Status Exec Time Memory
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 1 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 2 ms 256 KB
02-01.txt AC 31 ms 768 KB
02-02.txt AC 39 ms 1408 KB
02-03.txt AC 31 ms 512 KB
02-04.txt AC 41 ms 1280 KB
02-05.txt AC 40 ms 1280 KB
02-06.txt AC 40 ms 1280 KB
02-07.txt AC 42 ms 1408 KB
02-08.txt AC 33 ms 1408 KB
02-09.txt AC 47 ms 1792 KB
02-10.txt AC 37 ms 1024 KB
02-11.txt AC 37 ms 1024 KB
02-12.txt AC 36 ms 1024 KB
02-13.txt AC 36 ms 1024 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB