Submission #1696412


Source Code Expand

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

class Main {

    public static void main(String[] args) {
        new Main().compute();
    }

    void compute() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        List<Integer>[] adjacents = new List[N];
        for (int i = 0; i < N; i++) {
            adjacents[i] = new ArrayList<>();
        }
        for (int i = 0; i < N - 1; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            adjacents[a].add(b);
            adjacents[b].add(a);
        }
        int[] fromFennec = new int[N];
        Arrays.fill(fromFennec, N);
        Stack<Integer> stk = new Stack<>();
        fromFennec[0] = 0;
        stk.push(0);
        while (!stk.empty()) {
            int start = stk.pop();
            int dist = fromFennec[start] + 1;
            for (int i : adjacents[start]) {
                if (fromFennec[i] == N) {
                    fromFennec[i] = dist;
                    stk.push(i);
                }
            }
        }
        int[] fromSnuke = new int[N];
        Arrays.fill(fromSnuke, N);
        fromSnuke[N - 1] = 0;
        stk.push(N - 1);
        while (!stk.empty()) {
            int start = stk.pop();
            int dist = fromSnuke[start] + 1;
            for (int i : adjacents[start]) {
                if (fromSnuke[i] == N) {
                    fromSnuke[i] = dist;
                    stk.push(i);
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < N; i++) {
            if (fromFennec[i] > fromSnuke[i]) {
                sum++;
            }
        }
        if (sum >= N - sum) {
            System.out.println("Snuke");
        } else {
            System.out.println("Fennec");
        }
    }
}

Submission Info

Submission Time
Task D - Fennec VS. Snuke
User packer_jp
Language Java8 (OpenJDK 1.8.0)
Score 400
Code Size 2085 Byte
Status AC
Exec Time 725 ms
Memory 105128 KB

Compile Error

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 21
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt
All 00_example_01.txt, 00_example_02.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 92 ms 19924 KB
00_example_02.txt AC 101 ms 21716 KB
01.txt AC 95 ms 18896 KB
02.txt AC 93 ms 21716 KB
03.txt AC 94 ms 20692 KB
04.txt AC 96 ms 21076 KB
05.txt AC 630 ms 75956 KB
06.txt AC 682 ms 88368 KB
07.txt AC 660 ms 78272 KB
08.txt AC 670 ms 86324 KB
09.txt AC 92 ms 21588 KB
10.txt AC 646 ms 77832 KB
11.txt AC 634 ms 86696 KB
12.txt AC 629 ms 85604 KB
13.txt AC 725 ms 105128 KB
14.txt AC 705 ms 102376 KB
15.txt AC 652 ms 94596 KB
16.txt AC 669 ms 103012 KB
17.txt AC 672 ms 102528 KB
18.txt AC 704 ms 101456 KB
19.txt AC 674 ms 101012 KB