# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
381144 |
2021-03-24T16:23:28 Z |
vijay |
Triumphal arch (POI13_luk) |
Java 11 |
|
2000 ms |
76356 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);
// 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 = 0;
int b = N - 1;
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 |
129 ms |
11164 KB |
Output is correct |
2 |
Correct |
124 ms |
10392 KB |
Output is correct |
3 |
Incorrect |
130 ms |
10368 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
127 ms |
10268 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
165 ms |
11104 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
322 ms |
13784 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
742 ms |
19536 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
860 ms |
22196 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1221 ms |
36528 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1752 ms |
54768 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2073 ms |
76356 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2039 ms |
76128 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |