Submission #3222882


Source Code Expand

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.Set;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.TreeSet;
import java.util.Map;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author prakharjain
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        agc014d solver = new agc014d();
        solver.solve(1, in, out);
        out.close();
    }

    static class agc014d {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();

            Set[] g = new Set[n];

            for (int i = 0; i < n; i++) {
                g[i] = new TreeSet();
            }

            for (int i = 0; i < n - 1; i++) {
                int a = in.nextInt();
                int b = in.nextInt();

                a--;
                b--;

                g[a].add(b);
                g[b].add(a);
            }

            TreeSet<Integer> leaves = new TreeSet<>();

            for (int i = 0; i < n; i++) {
                int l = 0;
                for (int v : (Set<Integer>) g[i]) {
                    if (g[v].size() == 1) {
                        l++;
                        leaves.add(v);
                    }
                }

                if (l > 1) {
                    out.println("First");
                    return;
                }
            }

//        if (n % 2 == 1) {
//            out.println("First");
//        } else {
//            out.println("Second");
//        }

            Map<Integer, Integer> mp = new HashMap<>();

            int rn = n;

            while (rn > 1) {
                Map<Integer, Integer> nmp = new HashMap<>();

                TreeSet<Integer> nleaves = new TreeSet<>();

                for (int l : leaves) {
                    if (g[l].size() == 1) {
                        int v = ((TreeSet<Integer>) g[l]).first();
                        g[v].remove(l);
                        rn--;
                        nmp.merge(v, 1, (x, y) -> x + y);
                        nleaves.add(v);
                        if (mp.getOrDefault(l, 0) > 1) {
                            out.println("First");
                            return;
                        }
                    }
                }

                leaves = nleaves;
                mp = nmp;
            }

            out.println("Second");
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

Submission Info

Submission Time
Task D - Black and White Tree
User leashptntl
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 5767 Byte
Status WA
Exec Time 500 ms
Memory 71744 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 0 / 900
Status
AC × 3
AC × 29
WA × 10
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
in1.txt AC 204 ms 57016 KB
in10.txt AC 190 ms 56728 KB
in11.txt WA 492 ms 71744 KB
in12.txt WA 221 ms 26200 KB
in13.txt WA 483 ms 71208 KB
in14.txt WA 487 ms 69240 KB
in15.txt WA 452 ms 68788 KB
in16.txt WA 453 ms 68032 KB
in17.txt WA 473 ms 68620 KB
in18.txt WA 500 ms 70924 KB
in19.txt WA 490 ms 68292 KB
in2.txt AC 182 ms 56676 KB
in20.txt WA 492 ms 69996 KB
in21.txt AC 194 ms 56376 KB
in22.txt AC 191 ms 55524 KB
in23.txt AC 196 ms 56380 KB
in24.txt AC 216 ms 56120 KB
in25.txt AC 196 ms 55540 KB
in26.txt AC 491 ms 68232 KB
in27.txt AC 193 ms 53204 KB
in28.txt AC 157 ms 25812 KB
in29.txt AC 478 ms 69800 KB
in3.txt AC 182 ms 55100 KB
in30.txt AC 488 ms 70296 KB
in31.txt AC 493 ms 67668 KB
in32.txt AC 445 ms 66100 KB
in33.txt AC 478 ms 70976 KB
in4.txt AC 191 ms 56532 KB
in5.txt AC 191 ms 54112 KB
in6.txt AC 194 ms 54696 KB
in7.txt AC 188 ms 54448 KB
in8.txt AC 191 ms 51764 KB
in9.txt AC 205 ms 56884 KB
sample1.txt AC 73 ms 20436 KB
sample2.txt AC 80 ms 21332 KB
sample3.txt AC 153 ms 23892 KB