| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 653026 |
2022-10-25T13:06:38 Z |
beaconmc |
Race (IOI11_race) |
C++14 |
|
1049 ms |
64912 KB |
#include <bits/stdc++.h>
#include "race.h"
#define ll long long
#define FOR(i,x,y) for(ll i=x; i<y; i++)
using namespace std;
bool r[300000];
vector<vector<ll>> edges[300000];
ll sub[300000];
ll n,m,root,k;
vector<vector<ll>> twosum;
ll ans = 1000000000;
ll dfs(ll a, ll p){
sub[a] = 1;
for (auto& i : edges[a]){
if (i[0]!=p && !r[i[0]]) sub[a] += dfs(i[0], a);
}
return sub[a];
}
void dfs2(ll a, ll p, ll v, ll num, ll col){
for (auto& i : edges[a]){
if (i[0]!=p && !r[i[0]]) dfs2(i[0], a, v+i[1], num+1, col);
}
twosum.push_back({v, num, col});
}
ll centroid(ll a, ll sz, ll p){
for (auto&i : edges[a]){
if (i[0]!=p && !r[i[0]] && sub[i[0]]*2 > sz){
return centroid(i[0], sz, a);
}
}
return a;
}
void decomp(ll a, ll p){
ll c = centroid(a, dfs(a, -1), -1);
twosum.clear();
ll col = 0;
for (auto&i : edges[c]){
if (!r[i[0]]) dfs2(i[0], c, i[1],1,col);
twosum.push_back({0,0,col});
col++;
}
sort(twosum.begin(), twosum.end());
ll lo = 0;
ll hi = twosum.size()-1;
while (lo<=hi){
if (twosum[lo][0] + twosum[hi][0] > k){
hi--;
}else if (twosum[lo][0] + twosum[hi][0] == k){
if (twosum[lo][2] == twosum[hi][2]){
if (twosum[hi][0] != twosum[hi-1][0]){
lo++;
continue;
}
hi--;
continue;
}else{
ans = min(ans, twosum[lo][1] + twosum[hi][1]);
hi --;
}
}else if (twosum[lo][0] + twosum[hi][0] < k){
lo++;
}
}
r[c] = 1;
for (auto&i : edges[c]){
if (!r[i[0]]) decomp(i[0], c);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
FOR(i,0,n-1){
ll a,b,c;
a = H[i][0];
b = H[i][1];
c = L[i];
edges[a].push_back({b,c});
edges[b].push_back({a,c});
}
decomp(0,-1);
if (ans == 1000000000) ans = -1;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7360 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7364 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 8 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 12 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 13 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 14 |
Correct |
5 ms |
7360 KB |
Output is correct |
| 15 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 16 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 17 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7360 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7364 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 8 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 12 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 13 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 14 |
Correct |
5 ms |
7360 KB |
Output is correct |
| 15 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 16 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 17 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 19 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 20 |
Correct |
4 ms |
7364 KB |
Output is correct |
| 21 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 22 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 23 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 24 |
Correct |
6 ms |
7500 KB |
Output is correct |
| 25 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 26 |
Correct |
6 ms |
7504 KB |
Output is correct |
| 27 |
Correct |
5 ms |
7504 KB |
Output is correct |
| 28 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 29 |
Correct |
8 ms |
7592 KB |
Output is correct |
| 30 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 31 |
Correct |
5 ms |
7504 KB |
Output is correct |
| 32 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 33 |
Correct |
6 ms |
7500 KB |
Output is correct |
| 34 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 35 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 36 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 37 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 38 |
Correct |
6 ms |
7496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7360 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7364 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 8 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 12 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 13 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 14 |
Correct |
5 ms |
7360 KB |
Output is correct |
| 15 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 16 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 17 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 19 |
Correct |
412 ms |
28960 KB |
Output is correct |
| 20 |
Correct |
401 ms |
29116 KB |
Output is correct |
| 21 |
Correct |
424 ms |
29056 KB |
Output is correct |
| 22 |
Correct |
353 ms |
28984 KB |
Output is correct |
| 23 |
Correct |
330 ms |
29668 KB |
Output is correct |
| 24 |
Correct |
189 ms |
28092 KB |
Output is correct |
| 25 |
Correct |
356 ms |
35812 KB |
Output is correct |
| 26 |
Correct |
273 ms |
35916 KB |
Output is correct |
| 27 |
Correct |
435 ms |
50804 KB |
Output is correct |
| 28 |
Correct |
865 ms |
64684 KB |
Output is correct |
| 29 |
Correct |
843 ms |
64532 KB |
Output is correct |
| 30 |
Correct |
440 ms |
50644 KB |
Output is correct |
| 31 |
Correct |
438 ms |
50700 KB |
Output is correct |
| 32 |
Correct |
535 ms |
50696 KB |
Output is correct |
| 33 |
Correct |
682 ms |
50540 KB |
Output is correct |
| 34 |
Correct |
669 ms |
51240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7360 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7364 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 8 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 9 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 10 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 12 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 13 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 14 |
Correct |
5 ms |
7360 KB |
Output is correct |
| 15 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 16 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 17 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 19 |
Correct |
5 ms |
7364 KB |
Output is correct |
| 20 |
Correct |
4 ms |
7364 KB |
Output is correct |
| 21 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 22 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 23 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 24 |
Correct |
6 ms |
7500 KB |
Output is correct |
| 25 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 26 |
Correct |
6 ms |
7504 KB |
Output is correct |
| 27 |
Correct |
5 ms |
7504 KB |
Output is correct |
| 28 |
Correct |
6 ms |
7508 KB |
Output is correct |
| 29 |
Correct |
8 ms |
7592 KB |
Output is correct |
| 30 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 31 |
Correct |
5 ms |
7504 KB |
Output is correct |
| 32 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 33 |
Correct |
6 ms |
7500 KB |
Output is correct |
| 34 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 35 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 36 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 37 |
Correct |
5 ms |
7508 KB |
Output is correct |
| 38 |
Correct |
6 ms |
7496 KB |
Output is correct |
| 39 |
Correct |
412 ms |
28960 KB |
Output is correct |
| 40 |
Correct |
401 ms |
29116 KB |
Output is correct |
| 41 |
Correct |
424 ms |
29056 KB |
Output is correct |
| 42 |
Correct |
353 ms |
28984 KB |
Output is correct |
| 43 |
Correct |
330 ms |
29668 KB |
Output is correct |
| 44 |
Correct |
189 ms |
28092 KB |
Output is correct |
| 45 |
Correct |
356 ms |
35812 KB |
Output is correct |
| 46 |
Correct |
273 ms |
35916 KB |
Output is correct |
| 47 |
Correct |
435 ms |
50804 KB |
Output is correct |
| 48 |
Correct |
865 ms |
64684 KB |
Output is correct |
| 49 |
Correct |
843 ms |
64532 KB |
Output is correct |
| 50 |
Correct |
440 ms |
50644 KB |
Output is correct |
| 51 |
Correct |
438 ms |
50700 KB |
Output is correct |
| 52 |
Correct |
535 ms |
50696 KB |
Output is correct |
| 53 |
Correct |
682 ms |
50540 KB |
Output is correct |
| 54 |
Correct |
669 ms |
51240 KB |
Output is correct |
| 55 |
Correct |
21 ms |
9624 KB |
Output is correct |
| 56 |
Correct |
24 ms |
9552 KB |
Output is correct |
| 57 |
Correct |
278 ms |
29480 KB |
Output is correct |
| 58 |
Correct |
108 ms |
33104 KB |
Output is correct |
| 59 |
Correct |
296 ms |
35800 KB |
Output is correct |
| 60 |
Correct |
1049 ms |
64404 KB |
Output is correct |
| 61 |
Correct |
499 ms |
50976 KB |
Output is correct |
| 62 |
Correct |
514 ms |
50864 KB |
Output is correct |
| 63 |
Correct |
594 ms |
50732 KB |
Output is correct |
| 64 |
Correct |
1022 ms |
51448 KB |
Output is correct |
| 65 |
Correct |
847 ms |
51880 KB |
Output is correct |
| 66 |
Correct |
900 ms |
64912 KB |
Output is correct |
| 67 |
Correct |
322 ms |
60256 KB |
Output is correct |
| 68 |
Correct |
556 ms |
50256 KB |
Output is correct |
| 69 |
Correct |
555 ms |
50724 KB |
Output is correct |
| 70 |
Correct |
566 ms |
48508 KB |
Output is correct |
