CODE FESTIVAL 2016 Final

Submission #11216832

Source codeソースコード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final int m = scanner.nextInt();

        final UnionFindTree tree = new UnionFindTree(n);
        final int[] langToMan = new int[m + 1];
        Arrays.fill(langToMan, -1);
        for (int man = 1; man <= n; man++) {
            final int k = scanner.nextInt();
            for (int j = 0; j < k; j++) {
                final int lang = scanner.nextInt();
                if (langToMan[lang] == -1) {
                    langToMan[lang] = man;
                } else {
                    tree.unit(man, langToMan[lang]);
                }
            }
        }

        final boolean answer = IntStream.rangeClosed(1, n)
                .mapToObj(tree::getRoot)
                .allMatch(v -> v == 1);

        System.out.println(answer ? "YES" : "NO");
    }

    private static class UnionFindTree {
        private Integer[] nodes;
        private final List<Integer> indices = new ArrayList<>();

        UnionFindTree(final int numOfNodes) {
            this.nodes = init(numOfNodes);
        }

        private Integer[] init(final int numOfNodes) {
            return IntStream.rangeClosed(0, numOfNodes)
                    .boxed()
                    .toArray(Integer[]::new);
        }

        int getRoot(final int nodeNumber) {
            final int rootNode = nodes[nodeNumber];
            if (rootNode == nodeNumber) {
                for (final Integer index : indices) {
                    nodes[index] = rootNode;
                }
                indices.clear();
                return nodeNumber;
            }

            indices.add(nodeNumber);
            return getRoot(rootNode);
        }

        boolean isSame(final int nodeA, final int nodeB) {
            return getRoot(nodeA) == getRoot(nodeB);
        }

        void unit(final int nodeA, final int nodeB) {
            final int rootA = getRoot(nodeA);
            final int rootB = getRoot(nodeB);

            if (rootA == rootB) {
                return;
            }

            nodes[Math.max(rootA, rootB)] = Math.min(rootA, rootB);
        }
    }
}

Submission

Task問題 C - Interpretation
User nameユーザ名 T45K
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 400
Source lengthソースコード長 2451 Byte
File nameファイル名
Exec time実行時間 685 ms
Memory usageメモリ使用量 94920 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 193 ms 25428 KB
01-02.txt AC 215 ms 24804 KB
01-03.txt AC 225 ms 26896 KB
01-04.txt AC 227 ms 27220 KB
01-05.txt AC 236 ms 25432 KB
01-06.txt AC 213 ms 25060 KB
01-07.txt AC 227 ms 25780 KB
01-08.txt AC 221 ms 24916 KB
01-09.txt AC 241 ms 25436 KB
01-10.txt AC 236 ms 27220 KB
02-01.txt AC 535 ms 49680 KB
02-02.txt AC 667 ms 80936 KB
02-03.txt AC 551 ms 53632 KB
02-04.txt AC 650 ms 65444 KB
02-05.txt AC 644 ms 77840 KB
02-06.txt AC 588 ms 63692 KB
02-07.txt AC 684 ms 93976 KB
02-08.txt AC 665 ms 94920 KB
02-09.txt AC 685 ms 92316 KB
02-10.txt AC 609 ms 64872 KB
02-11.txt AC 587 ms 65308 KB
02-12.txt AC 615 ms 63556 KB
02-13.txt AC 579 ms 65368 KB
sample-01.txt AC 186 ms 24788 KB
sample-02.txt AC 190 ms 25040 KB