# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
832669 | 2023-08-21T13:31:02 Z | aymanrs | Towns (IOI15_towns) | C++14 | 15 ms | 468 KB |
#include "towns.h" #include <bits/stdc++.h> using namespace std; int hubDistance(int N, int sub) { int md = 0, wi = 1, wii; for(int i = 1;i < N;i++){ int c = getDistance(0, i); if(c > md){ md = c; wi = i; } } int d[N], dw[N]; d[wi]=0; md = 0; wii = 0; for(int i = 0;i < N;i++){ if(i == wi) continue; d[i] = getDistance(wi, i); if(d[i] > md){ md = d[i]; wii = i; } } dw[wii] = 0; dw[wi] = md; for(int i = 0;i < N;i++) if(i != wi && i != wii) dw[i] = getDistance(wii, i); for(int i = 0;i < N;i++){ if(i == wi || i == wii) continue; int dlca = (d[i]+dw[i]-d[wii])/2; md = min(md, max(d[i]-dlca, dw[i]-dlca)); } int C[2][2]; for(int i = 0;i < N;i++){ if(i == wi){ C[0][0]++; continue; } if(i == wii){ C[1][0]++; continue; } int dlca = (d[i]+dw[i]-d[wii])/2; dlca = max(d[i]-dlca, dw[i]-dlca); C[d[i] < dw[i]][dlca==md]++; } N/=2; if(!C[0][1]) goto st; if(C[0][1]-1 <= N && C[0][0] <= N && C[1][0]+C[1][1] <= N) return md; st: if(!C[1][1]) return -md; if(C[1][1]-1 <= N && C[1][0] <= N && C[0][0]+C[0][1] <= N) return md; return -md; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 468 KB | Output is correct |
2 | Correct | 9 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 12 ms | 336 KB | Output is correct |
5 | Correct | 11 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 340 KB | Output is correct |
2 | Correct | 8 ms | 340 KB | Output is correct |
3 | Correct | 11 ms | 340 KB | Output is correct |
4 | Correct | 11 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 8 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 14 ms | 344 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |