Submission #669657

#	Time	Username	Problem	Language	Result	Execution time	Memory
669657		ziduo	Mousetrap (CEOI17_mousetrap)	Java	0 / 100	1229 ms	191612 KiB

mousetrap

import java.io.*;
import java.util.*;
public class mousetrap {
	static ArrayList<Integer>[] edges;
	static int[] dp;
	static int[] par;
	static ArrayList<int[]> list;
	public static void main(String[] args)throws IOException {
		// TODO Auto-generated method stub
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    int n = Integer.parseInt(st.nextToken());
	    int t = Integer.parseInt(st.nextToken())-1;
	    int m = Integer.parseInt(st.nextToken())-1;
	    edges = new ArrayList[n];
	    for(int i=0; i<n; i++)edges[i] = new ArrayList<>();
	    for(int i=0; i<n-1; i++) {
	    	st = new StringTokenizer(br.readLine());
	    	int a = Integer.parseInt(st.nextToken())-1;
	    	int b = Integer.parseInt(st.nextToken())-1;
	    	edges[a].add(b);
	    	edges[b].add(a);
	    }
	    int p = m;
	    dp = new int[n];
	    list = new ArrayList<>();
	    par = new int[n];
	    par[t]= -1;
	    	//Integer.parseInt(st.nextToken());
	    	//Integer.parseInt(br.readLine());
	    dfs(t);
	    while(m!=t) {
	    	list.add(new int[] {m,0});
	    	m = par[m];
	    }
	    int c= 0;
	    for(int i= list.size()-1; i>0; i--) {
	    	c++;
	    	for(int v: edges[list.get(i)[0]])
	    		if(v!=par[list.get(i)[0]]&&v!=list.get(i-1)[0])
	    			c--;
	    	if(c>0)c=0;
	    	list.get(i)[1]=-c;
	    }
	    c++;
	    if(c>0)c=0;
	    list.get(0)[1]=-c;
	    int l = 0;
	    int r = 1000000000;
	    while(l<=r) {
	    	int mid = (l+r)/2;
	    	if(check(mid))
	    		l = mid+1;
	    	else 
	    		r = mid-1;
	    }
	    if(!check(l))l--;
	    int ans = Math.max(l, dp[p]+list.get(0)[1]+list.size());
	    out.write(ans+"\n");
	    out.flush();
	    out.close();
	}
	static boolean check(int val) {
		int c = 0;
		for(int i=1; i<list.size(); i++) {
			c++;
	    	for(int v: edges[list.get(i)[0]])
	    		if(v!=par[list.get(i)[0]]&&v!=list.get(i-1)[0])
	    			if(dp[v]+2+list.size()+list.get(i)[1]>=val) 
	    				c--;
	    	if(c<0)return true;
		}
		return false;
	}
	static void dfs(int n) {
		int[] mins = new int[] {-1,-1};
		for(int v: edges[n]) {
			if(v==par[n])continue;
			par[v]=n;
			dfs(v);
			if(mins[0]==-1||dp[n]<mins[0]) {
				mins[1]=mins[0];
				mins[0]=dp[n];
			}
			else if(mins[1]==-1||dp[n]<mins[1]) 
				mins[1]=dp[n];
		}
		if(mins[1]==-1)dp[n]=0;
		else dp[n]=mins[1]+2;
	}
}

Compilation message (stderr)

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

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35