CODE FESTIVAL 2016 Final

Submission #6326256

Source codeソースコード

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, l-1);
        }
    }

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

Submission

Task問題 C - Interpretation
User nameユーザ名 cedretaber
Created time投稿日時
Language言語 D (DMD64 v2.070.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 1766 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,sample-01.txt,sample-02.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 1 ms 256 KB
01-02.txt AC 1 ms 380 KB
01-03.txt AC 2 ms 508 KB
01-04.txt AC 2 ms 508 KB
01-05.txt WA
01-06.txt AC 2 ms 380 KB
01-07.txt AC 2 ms 380 KB
01-08.txt WA
01-09.txt AC 2 ms 380 KB
01-10.txt AC 2 ms 508 KB
02-01.txt AC 34 ms 4476 KB
02-02.txt WA
02-03.txt WA
02-04.txt AC 75 ms 4604 KB
02-05.txt AC 85 ms 4092 KB
02-06.txt AC 73 ms 3836 KB
02-07.txt AC 91 ms 2428 KB
02-08.txt WA
02-09.txt AC 100 ms 4732 KB
02-10.txt AC 60 ms 5508 KB
02-11.txt WA
02-12.txt AC 61 ms 4348 KB
02-13.txt WA
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB