Submission #1696307


Source Code Expand

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();
        boolean[][] mat = new boolean[N][N];
        for (int i = 0; i < N - 1; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            mat[a][b] = true;
            mat[b][a] = true;
        }
        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 = 0; i < N; i++) {
                if (mat[start][i] && fromFennec[i] == N) {
                    fromFennec[i] = dist;
                    stk.push(i);
                }
            }
        }
        int[] fromSnuke = new int[N];
        Arrays.fill(fromSnuke, N);
        stk = new Stack<>();
        fromSnuke[N - 1] = 0;
        stk.push(N - 1);
        while (!stk.empty()) {
            int start = stk.pop();
            int dist = fromSnuke[start] + 1;
            for (int i = 0; i < N; i++) {
                if (mat[start][i] && 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 / 2) {
            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 0
Code Size 1975 Byte
Status WA
Exec Time 1071 ms
Memory 941560 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 2
AC × 5
WA × 2
MLE × 14
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 102 ms 19924 KB
00_example_02.txt AC 102 ms 20556 KB
01.txt AC 101 ms 20564 KB
02.txt AC 101 ms 21972 KB
03.txt WA 105 ms 21716 KB
04.txt WA 101 ms 21332 KB
05.txt MLE 1033 ms 932700 KB
06.txt MLE 1071 ms 934856 KB
07.txt MLE 906 ms 935052 KB
08.txt MLE 860 ms 941560 KB
09.txt AC 101 ms 22608 KB
10.txt MLE 880 ms 932876 KB
11.txt MLE 847 ms 941256 KB
12.txt MLE 856 ms 936888 KB
13.txt MLE 833 ms 870540 KB
14.txt MLE 826 ms 870948 KB
15.txt MLE 856 ms 931992 KB
16.txt MLE 806 ms 870456 KB
17.txt MLE 796 ms 874012 KB
18.txt MLE 807 ms 869928 KB
19.txt MLE 806 ms 877708 KB