Submission #283528

#	Time	Username	Problem	Language	Result	Execution time	Memory
283528		ijxjdjd	Network (BOI15_net)	Java	63 / 100	2021 ms	116008 KiB

net

import java.util.*;
import java.io.*;
public class net {
  static ArrayList<Integer>[] adj;
    public static void main(String[] args) {
        try {
            Reader r = new Reader();
            int N = r.nextInt();
            adj = new ArrayList[N];
            for (int i = 0; i < N; i++) {
                adj[i] = new ArrayList<>();
            }
            for (int i = 0; i < N - 1; i++) {
                int a = r.nextInt() - 1;
                int b = r.nextInt() - 1;
                adj[a].add(b);
                adj[b].add(a);
            }
            if (N == 2) {
                System.out.println("1\n1 2");
            } else {
                for (int i = 0; i < N; i++) {
                    if (adj[i].size() > 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;
                    }
                }
                System.out.println(ans.size());
                for (Set s : ans) {
                    System.out.println((s.a1 + 1) + " " + (s.a2 + 1));
                }
            }
        }
        catch (IOException e) {
 
        }
    }
    static ArrayList<Set> ans = new ArrayList<>();
    static 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;
    }
    static 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].size()) {
                return -1;
            } else if (adj[n].get(cur) == p) {
                cur++;
                return getNext();
            }
            else {
                return adj[n].get(cur++);
            }
        }
        void merge(Set s) {
            if (this.s == null) {
                this.s = s;
            }
            else {
                this.s.merge(s);
            }
        }
    }
    static 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, 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 String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }
 
        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;
        }
 
        public long nextLong() throws IOException
        {
            long 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;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            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 (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            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++];
        }
 
    }
}

Compilation message (stderr)

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

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