Submission #413838

#	Time	Username	Problem	Language	Result	Execution time	Memory
413838		TruaShamu	Torrent (COI16_torrent)	Java	0 / 100	2052 ms	136208 KiB

torrent

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class torrent {
    public static ArrayList<Edge>[] adj;
    public static ArrayList<Integer> path = new ArrayList<>();
    public static ArrayList<Integer> temp = new ArrayList<>();
    public static int N, A, B;
    public static int cutEdge;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        A = Integer.parseInt(st.nextToken()) - 1;
        B = Integer.parseInt(st.nextToken()) - 1;

        adj = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            adj[i] = new ArrayList<>();
        }

        //@todo Read edges
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            adj[x].add(new Edge(y, i));
            adj[y].add(new Edge(x, i));
        }



        //@todo DFS to find a path from A to B
        dfsFindPath(A, -1);

        //@todo
        int left = 0;
        int right = path.size() - 1;
        int last = 0;

        
        while (left <= right) {
            int mid = (left + right) >> 1;
            cutEdge = path.get(mid);
            int ansA = solve(A, -1);
            int ansB = solve(B, -1);
            if (ansA <= ansB) {
                last = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        cutEdge = path.get(last);

        int ans = Math.max(solve(A, -1), solve(B, -1));
        if (last + 1 < path.size()) {
            cutEdge = path.get(last + 1);
            ans = Math.min(ans, Math.max(solve(A, -1), solve(B, -1)));
        }

        System.out.println(ans);
    }

    public static void dfsFindPath(int cur, int par) {
        if (!path.isEmpty()) {
            return;
        }
        if (cur == B) {
            path = new ArrayList<>(temp);
            return;
        }
        for (Edge oEdge : adj[cur]) {
            int next = oEdge.to;
            if (next == par) {
                continue;
            }
            temp.add(oEdge.idx);
            dfsFindPath(next, cur);
            temp.remove(temp.size() - 1);
        }
    }

    public static int solve(int cur, int par) {
        int ans = 0;
        ArrayList<Integer> V = new ArrayList<>();
        for (Edge oEdge : adj[cur]) {
            int next = oEdge.to;
            if (next == par) {
                continue;
            }
            if (oEdge.idx == cutEdge) {
                continue;
            }
            V.add(solve(next, cur));
        }
        Collections.sort(V);
        for (int i = 0; i < V.size(); i++) {
            ans = Math.max(ans, (V.get(i) + i + 1));
        }
        return ans;
    }

    static class Edge {
        int to;
        int idx;

        public Edge(int to, int idx) {
            this.to = to;
            this.idx = idx;
        }

    }
}

Compilation message (stderr)

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

• Subtask 1: 0 / 31
• Subtask 2: 0 / 69