Submission #283536

#	Time	Username	Problem	Language	Result	Execution time	Memory
283536		ijxjdjd	Network (BOI15_net)	Java	100 / 100	1117 ms	89872 KiB

net

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.DataInputStream;
import java.io.IOException;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.ArrayList;
import java.util.Vector;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

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

    static class Network {
        int[][] adj;
        ArrayList<Set> ans = new ArrayList<>();

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            try {
                Network.Reader r = new Network.Reader();
                int N = r.nextInt();
                adj = new int[N][];
                int[] from = new int[N - 1];
                int[] to = new int[N - 1];
                for (int i = 0; i < N - 1; i++) {
                    int a = r.nextInt() - 1;
                    int b = r.nextInt() - 1;
                    from[i] = a;
                    to[i] = b;
                }
                adj = DefaultTree.packU(N, from, to);
                if (N == 2) {
                    out.println("1\n1 2");
                } else {
                    for (int i = 0; i < N; i++) {
                        if (adj[i].length > 1) {
                            Set f = dfs(i);
                            if (f.a2 == -1) {
                                ans.add(new Set(f.a1, i));
                            } else {
                                ans.add(new Set(f.a1, f.a2));
                            }
                            break;
                        }
                    }
                    out.println(ans.size());
                    for (Set s : ans) {
                        out.println((s.a1 + 1) + " " + (s.a2 + 1));
                    }
                }
            } catch (IOException e) {

            }
        }

        Set dfs(int n) {
            Stack<State> stack = new Stack<>();
            stack.add(new State(n, n));
            while (stack.size() > 0) {
                State next = stack.peek();
                int a = next.getNext();
                if (a == -1) {
                    stack.pop();
                    if (stack.isEmpty()) {
                        return next.s;
                    }
                    if (next.cur == 1) {
                        stack.peek().merge(new Set(next.n));
                    } else {
                        stack.peek().merge(next.s);
                    }
                } else {
                    stack.add(new State(a, next.n));
                }
            }
            return null;
        }

        class State {
            int cur;
            int n;
            int p;
            Set s = null;

            State(int n, int p) {
                cur = 0;
                this.n = n;
                this.p = p;
            }

            int getNext() {
                if (cur >= adj[n].length) {
                    return -1;
                } else if (adj[n][cur] == p) {
                    cur++;
                    return getNext();
                } else {
                    return adj[n][cur++];
                }
            }

            void merge(Set s) {
                if (this.s == null) {
                    this.s = s;
                } else {
                    this.s.merge(s);
                }
            }

        }

        class Set {
            int a1;
            int a2;

            void merge(Set s) {
                if (s.a2 == -1 && this.a2 == -1) {
                    this.a2 = s.a1;
                } else if (s.a2 == -1) {
                    ans.add(new Set(s.a1, this.a2));
                    this.a2 = -1;
                } else if (this.a2 == -1) {
                    ans.add(new Set(this.a1, s.a2));
                    this.a1 = s.a1;
                } else {
                    ans.add(new Set(this.a1, s.a1));
                    this.a1 = this.a2;
                    this.a2 = s.a2;
                }
            }

            Set(int a) {
                this.a1 = a;
                this.a2 = -1;
            }

            Set(int a, int b) {
                this.a1 = a;
                this.a2 = b;
            }

        }

        static class Reader {
            final private int BUFFER_SIZE = 1 << 16;
            private DataInputStream din;
            private byte[] buffer;
            private int bufferPointer;
            private int bytesRead;

            public Reader() {
                din = new DataInputStream(System.in);
                buffer = new byte[BUFFER_SIZE];
                bufferPointer = bytesRead = 0;
            }

            public Reader(String file_name) throws IOException {
                din = new DataInputStream(new FileInputStream(file_name));
                buffer = new byte[BUFFER_SIZE];
                bufferPointer = bytesRead = 0;
            }

            public int nextInt() throws IOException {
                int ret = 0;
                byte c = read();
                while (c <= ' ')
                    c = read();
                boolean neg = (c == '-');
                if (neg)
                    c = read();
                do {
                    ret = ret * 10 + c - '0';
                } while ((c = read()) >= '0' && c <= '9');

                if (neg)
                    return -ret;
                return ret;
            }

            private void fillBuffer() throws IOException {
                bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
                if (bytesRead == -1)
                    buffer[0] = -1;
            }

            private byte read() throws IOException {
                if (bufferPointer == bytesRead)
                    fillBuffer();
                return buffer[bufferPointer++];
            }

        }

    }

    static class DefaultTree {
        DefaultTree.Node[] tree;
        int K;
        int[][] lift;
        int[] tin;
        int[] tout;

        public DefaultTree(int N) {
            tree = new DefaultTree.Node[N];
            K = (int) Math.ceil(Math.log(N) / Math.log(2)) + 1;
            lift = new int[N][K];
            tin = new int[N];
            tout = new int[N];
            for (int i = 0; i < N; i++) {
                tree[i] = new DefaultTree.Node();
            }
        }

        public static int[][] packU(int N, int[] from, int[] to) {
            //undirected
            int[][] adj = new int[N][];
            int[] cntFrom = new int[N];
            for (int i = 0; i < from.length; i++) {
                cntFrom[from[i]]++;
                cntFrom[to[i]]++;
            }
            for (int i = 0; i < N; i++) {
                adj[i] = new int[cntFrom[i]];
            }
            for (int i = 0; i < from.length; i++) {
                adj[from[i]][--cntFrom[from[i]]] = to[i];
                adj[to[i]][--cntFrom[to[i]]] = from[i];
            }
            return adj;
        }

        static class Node {
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

    }
}

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37