Submission #6326265


Source Code Expand

Copy
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

struct UFTree(T)
{
    struct Node
    {
        T parent;
        T rank = 1;
    }

    ///
    this(T n)
    {
        nodes.length = n;
        sizes.length = n;
        foreach (i, ref node; nodes) {
            node = Node(i.to!T);
            sizes[i] = 1;
        }
    }

    ///
    bool unite(T a, T b)
    {
        a = root(a);
        b = root(b);

        if (a == b) return false;

        if (nodes[a].rank < nodes[b].rank) {
            sizes[nodes[a].parent] += sizes[nodes[b].parent];
            nodes[b].parent = nodes[a].parent;
        } else {
            sizes[nodes[b].parent] += sizes[nodes[a].parent];
            nodes[a].parent = nodes[b].parent;
            if (nodes[a].rank == nodes[b].rank) nodes[a].rank += 1;
        }

        return true;
    }

    ///
    bool is_same(T a, T b)
    {
        return root(a) == root(b);
    }

    ///
    T size(T i)
    {
        return sizes[root(i)];
    }

private:
    Node[] nodes;
    T[] sizes;

    T root(T i)
    {
        if (nodes[i].parent == i) return i;

        return nodes[i].parent = root(nodes[i].parent);
    }
}

///
UFTree!T uftree(T)(T n)
{
    return UFTree!T(n);
}

void main()
{
    auto nm = readln.split.to!(int[]);
    auto N = nm[0];
    auto M = nm[1];

    auto uft = uftree(N+M);

    foreach (int n; 0..N) {
        foreach (l; readln.split.to!(int[])[1..$]) {
            uft.unite(n, N+l-1);
        }
    }

    foreach (int i; 0..N-1) {
        if (!uft.is_same(i, i+1)) {
            writeln("NO");
            return;
        }
    }
    writeln("YES");
}

Submission Info

Submission Time
Task C - Interpretation
User cedretaber
Language D (DMD64 v2.070.1)
Score 400
Code Size 1768 Byte
Status
Exec Time 100 ms
Memory 7428 KB

Judge Result

Set Name Score / Max Score Test Cases
sample 0 / 0 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
Case Name Status Exec Time Memory
01-01.txt 1 ms 256 KB
01-02.txt 1 ms 380 KB
01-03.txt 2 ms 508 KB
01-04.txt 2 ms 508 KB
01-05.txt 2 ms 380 KB
01-06.txt 2 ms 380 KB
01-07.txt 2 ms 380 KB
01-08.txt 2 ms 380 KB
01-09.txt 2 ms 380 KB
01-10.txt 2 ms 508 KB
02-01.txt 33 ms 2556 KB
02-02.txt 94 ms 2428 KB
02-03.txt 38 ms 3580 KB
02-04.txt 73 ms 3324 KB
02-05.txt 86 ms 3324 KB
02-06.txt 71 ms 3452 KB
02-07.txt 93 ms 4092 KB
02-08.txt 92 ms 3964 KB
02-09.txt 100 ms 3580 KB
02-10.txt 61 ms 7428 KB
02-11.txt 61 ms 7136 KB
02-12.txt 61 ms 2940 KB
02-13.txt 60 ms 4860 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB