Submission #991676


Source Code Expand

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
int bsr(int x) { return 31 - __builtin_clz(x); }

struct UnionFind {
    vector<int> ig;
    vector<vector<int>> gi;
    int gn;
    UnionFind(int N) {
        ig.resize(N); gi.resize(N);
        for (int i = 0; i < N; i++) {
            ig[i] = i; gi[i] = {i};
        }
        gn = N;
    }
    void merge(int a, int b) {
        if (same(a, b)) return;
        gn--;
        int x = ig[a], y = ig[b];
        if (gi[x].size() < gi[y].size()) swap(x, y);
        for (int j: gi[y]) {
            ig[j] = x;
        }
        gi[x].insert(gi[x].end(), gi[y].begin(), gi[y].end());
        gi[y].clear();
    }
    bool same(int a, int b) {
        return ig[a] == ig[b];
    }
};


const int MN = 100100;
vector<int> g[MN];

int main() {
    ios::sync_with_stdio(0);
    cout << setprecision(20);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int x;
            cin >> x;
            g[x].push_back(i);
        }
    }
    UnionFind uf(n);
    for (int i = 0; i < MN; i++) {
        int l = int(g[i].size());
        for (int j = 0; j < l; j++) {
            int a = g[i][j];
            int b = g[i][(j+1)%l];
            uf.merge(a, b);
        }
    }
    if (uf.gn == 1) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task C - Interpretation
User yosupo
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1845 Byte
Status AC
Exec Time 44 ms
Memory 10880 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 200 / 200
Status
AC × 2
AC × 12
AC × 25
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
Case Name Status Exec Time Memory
01-01.txt AC 5 ms 2560 KB
01-02.txt AC 5 ms 2688 KB
01-03.txt AC 5 ms 2688 KB
01-04.txt AC 5 ms 2688 KB
01-05.txt AC 5 ms 2688 KB
01-06.txt AC 5 ms 2688 KB
01-07.txt AC 5 ms 2688 KB
01-08.txt AC 5 ms 2688 KB
01-09.txt AC 5 ms 2688 KB
01-10.txt AC 5 ms 2688 KB
02-01.txt AC 24 ms 4992 KB
02-02.txt AC 35 ms 9696 KB
02-03.txt AC 24 ms 4736 KB
02-04.txt AC 40 ms 8448 KB
02-05.txt AC 39 ms 8908 KB
02-06.txt AC 40 ms 8448 KB
02-07.txt AC 44 ms 10880 KB
02-08.txt AC 30 ms 9444 KB
02-09.txt AC 32 ms 9592 KB
02-10.txt AC 27 ms 7676 KB
02-11.txt AC 27 ms 7676 KB
02-12.txt AC 28 ms 7808 KB
02-13.txt AC 28 ms 7848 KB
sample-01.txt AC 5 ms 2560 KB
sample-02.txt AC 5 ms 2560 KB