# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
382631 |
2021-03-27T23:13:46 Z |
vijay |
Triumphal arch (POI13_luk) |
Java 11 |
|
2000 ms |
77380 KB |
import java.io.*;
import java.util.*;
public class luk {
static int N;
static int[] dayCount;
static ArrayList<Integer>[] adj;
public static void main(String[] args) throws IOException, FileNotFoundException {
Scanner in = new Scanner(System.in);
// Scanner in = new Scanner(new File("luk.in"));
// PrintWriter out = new PrintWriter("luk.out");
N = in.nextInt();
dayCount = new int[N];
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 = in.nextInt() - 1;
int b = in.nextInt() - 1;
adj[a].add(b);
adj[b].add(a);
}
recurse(0, 0, -1);
// System.out.println(Arrays.toString(dayCount));
// System.out.println(works(2));
int a = 1;
int b = N;
while(a != b){
int mid = (a + b)/2;
if(works(mid)){
b = mid;
} else {
a = mid + 1;
}
}
System.out.println(a);
}
static boolean works(int count){
int[] at = new int[count];
int pos = 0;
for(int dayPos = 1; dayPos < N; dayPos++){
for(int city = 0; city < dayCount[dayPos]; city++){
if(at[pos] >= dayPos){
return false;
}
at[pos]++;
pos++;
pos%=count;
}
}
return true;
}
static void recurse(int position, int day, int prev){
dayCount[day]++;
for(int ap: adj[position]){
if(ap != prev){
recurse(ap, day + 1, position);
}
}
}
}
Compilation message
Note: luk.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
119 ms |
10852 KB |
Output is correct |
2 |
Correct |
127 ms |
10496 KB |
Output is correct |
3 |
Incorrect |
125 ms |
10604 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
121 ms |
10348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
152 ms |
11228 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
325 ms |
13732 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
728 ms |
19528 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
811 ms |
21948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1146 ms |
36500 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1668 ms |
54736 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2031 ms |
77016 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2089 ms |
77380 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |