CODE FESTIVAL 2016 Final

Submission #11216550

Source codeソースコード

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
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 Map<Integer, List<Integer>> manToLang = new HashMap<>();
        final Map<Integer, List<Integer>> langToMan = new HashMap<>();
        for (int man = 1; man <= n; man++) {
            final int k = scanner.nextInt();
            for (int j = 0; j < k; j++) {
                final int lang = scanner.nextInt();
                manToLang.computeIfAbsent(man, v -> new ArrayList<>()).add(lang);
                langToMan.computeIfAbsent(lang, v -> new ArrayList<>()).add(man);
            }
        }

        final boolean[] manVisited = new boolean[n + 1];
        final boolean[] langVisited = new boolean[m + 1];
        dfs(manVisited, langVisited, 1, manToLang, langToMan);

        final boolean answer = IntStream.rangeClosed(1, n)
                .mapToObj(i -> manVisited[i])
                .allMatch(Boolean::booleanValue);

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

    private static void dfs(final boolean[] manVisited, final boolean[] langVisited, final int currentMan, final Map<Integer, List<Integer>> manToLang, final Map<Integer, List<Integer>> langToMan) {
        manVisited[currentMan] = true;

        for (final int lang : manToLang.get(currentMan)) {
            if (langVisited[lang]) {
                continue;
            }

            for (final int man : langToMan.get(lang)) {
                if (manVisited[man]) {
                    continue;
                }

                dfs(manVisited, langVisited, man, manToLang, langToMan);
            }
        }
    }

}

Submission

Task問題 C - Interpretation
User nameユーザ名 T45K
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 TLE
Score得点 200
Source lengthソースコード長 1961 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 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 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 194 ms 26708 KB
01-02.txt AC 234 ms 27232 KB
01-03.txt AC 244 ms 27852 KB
01-04.txt AC 293 ms 30436 KB
01-05.txt AC 246 ms 29072 KB
01-06.txt AC 245 ms 25684 KB
01-07.txt AC 245 ms 24800 KB
01-08.txt AC 242 ms 25444 KB
01-09.txt AC 239 ms 25172 KB
01-10.txt AC 317 ms 27356 KB
02-01.txt AC 687 ms 75804 KB
02-02.txt AC 861 ms 115956 KB
02-03.txt AC 712 ms 77552 KB
02-04.txt AC 782 ms 84708 KB
02-05.txt AC 785 ms 103260 KB
02-06.txt AC 749 ms 84416 KB
02-07.txt AC 843 ms 106320 KB
02-08.txt TLE
02-09.txt TLE
02-10.txt TLE
02-11.txt TLE
02-12.txt TLE
02-13.txt TLE
sample-01.txt AC 179 ms 28116 KB
sample-02.txt AC 182 ms 26960 KB