| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 314025 |
2020-10-18T00:07:10 Z |
KWang31 |
Torrent (COI16_torrent) |
Java 11 |
|
1853 ms |
149424 KB |
import java.io.*; import java.util.*;
public class torrent {
/**
* COI 16/4
* DP on tree + Binary Search
*/
static ArrayList<Integer> arl[];
static int[] par;
static int[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
int N=Integer.parseInt(st.nextToken());
int A=Integer.parseInt(st.nextToken())-1;
int B=Integer.parseInt(st.nextToken())-1;
arl=new ArrayList[N];
for (int i = 0; i < N; i++) {
arl[i]=new ArrayList<>();
}
int x,y;
for (int i = 0; i < N-1; i++) {
st=new StringTokenizer(br.readLine());
x=Integer.parseInt(st.nextToken())-1;
y=Integer.parseInt(st.nextToken())-1;
arl[x].add(y); arl[y].add(x);
}
//Step 1: Find the path between A and B with parent pointer
par=new int[N]; dp=new int[N];
dp(-1,-1,A); par[A]=-1;
dp(par[B],-1,B);
int BB=B; ArrayList<Integer> p=new ArrayList<>();//dp of nodes in the path
p.add(B);
int X=1;
while(par[BB]!=A){
//System.out.println(BB);
dp(BB,par[par[BB]],par[BB]);
X++;
p.add(par[BB]);
BB=par[BB];
}
p.add(A);
int[][] pref=new int[X+1][0]; int cnt=0;
//Add B first
pref[0]=new int[arl[B].size()-1];
for (int i : arl[B]) {
if(i!=par[B]){
pref[0][cnt]=dp[i]; cnt++;
}
}
Arrays.sort(pref[0]);
int cur,next;
for (int i = 1; i < X; i++) {
cur=p.get(i); next=p.get(i+1); cnt=0;
pref[i]=new int[arl[cur].size()-2];
for (int j : arl[cur]) {
if(j!=next && j!=p.get(i-1)){
pref[i][cnt]=dp[j]; cnt++;
}
}
Arrays.sort(pref[i]);
}
pref[X]=new int[arl[A].size()-1]; cnt=0;
for (int i : arl[A]) {
if(i!=BB){
pref[X][cnt]=dp[i];
cnt++;
}
}
Arrays.sort(pref[X]);
for (int i = 0; i <=X; i++) {
if(pref[i].length>0){
pref[i][0]++;
for (int j = 1; j < pref[i].length; j++) {
pref[i][j]=1+Math.max(pref[i][j-1],pref[i][j]);
}
}
}
int l=0; int r=dp[A];
while(l<r){
int m=(l+r)/2;
int ptDB=0; //Tracks which node B's pointer is on
int ptCB=pref[ptDB].length-1;
int ptDA=p.size()-1;
int ptCA=pref[ptDA].length-1;
boolean ok=false;
for (int mid=m; mid>0; mid--) {
if(m==2){
System.out.println(mid+" "+ptDB+" "+ptCB+" "+ptDA+" "+ptCA);
}
if(ptCB>=0 && pref[ptDB][ptCB]>mid){
break;
}else if(ptCB>0 && pref[ptDB][ptCB]==mid){
ptCB--;
}else{
ptDB++;ptCB=pref[ptDB].length-1;
}
if(ptCA>=0 && pref[ptDA][ptCA]>mid){
break;
}else if(ptCA>0 && pref[ptDA][ptCA]==mid){
ptCA--;
}else{
ptDA--; ptCA=pref[ptDA].length-1;
}
if(ptDB>ptDA){
ok=true; break;
}else if(ptDB==ptDA){
if(Math.min(ptCA,ptCB)==-1){
ok=true; break;
}else if(pref[ptDB][Math.min(ptCA,ptCB)]>mid-1){
break;
}else{
ok=true; break;
}
}
}
if(!ok){
l=m+1;
}else{
r=m;
}
//System.out.println(l+" "+r);
}
System.out.println(l);
}
public static void dp(int p, int p2, int v){
int[] c;
if(p>=0){
if(p2>=0){
c=new int[arl[v].size()-2];
}else{
c=new int[arl[v].size()-1];
}
}else{
c=new int[arl[v].size()];
}
int k=0;
for (int i : arl[v]) {
if(i==p || i==p2)continue;
dp(v,-1,i);
par[i]=v;
c[k]=dp[i]; k++;
}
Arrays.sort(c);
if(k==0){
dp[v]=0;
}else{
int max=c[k-1]+1;
for (int i = 2; i <= k; i++) {
max=Math.max(max,i+c[k-i]);
}
dp[v]=max;
}
}
}
Compilation message
Note: torrent.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
11872 KB |
Output is correct |
| 2 |
Correct |
116 ms |
11768 KB |
Output is correct |
| 3 |
Correct |
124 ms |
11768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1744 ms |
116616 KB |
Output is correct |
| 2 |
Correct |
1604 ms |
121372 KB |
Output is correct |
| 3 |
Correct |
1853 ms |
145000 KB |
Output is correct |
| 4 |
Correct |
1656 ms |
117016 KB |
Output is correct |
| 5 |
Correct |
1746 ms |
108528 KB |
Output is correct |
| 6 |
Correct |
1814 ms |
104476 KB |
Output is correct |
| 7 |
Correct |
1648 ms |
149424 KB |
Output is correct |
