# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
593833 |
2022-07-11T16:09:10 Z |
KrisjanisP |
Race (IOI11_race) |
C++14 |
|
499 ms |
29228 KB |
#include "race.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
using ll = int;
using ii = pair<ll,ll>;
const ll MXN = 2e5;
const ll MXK = 1e6;
vector<ii> AL[MXN];
bool removed[MXN];
ll N, K;
ll subtreeSize[MXN];
// get size of a subtree
ll getSize(ll v, ll p)
{
ll res = 1;
for(auto& [u,w]: AL[v])
{
if(u==p) continue;
if(removed[u]) continue;
res += getSize(u,v);
}
subtreeSize[v] = res;
return res;
}
// find the centroid
// of a connected component
ll findCentroid(ll v, ll p, ll n)
{
bool found = true;
ll sum = 1;
for(auto& [u,w]: AL[v])
{
if(u==p) continue;
if(removed[u]) continue;
sum += subtreeSize[u];
if(subtreeSize[u]>(n/2))
{
found = false;
break;
}
}
if((n-sum)>(n/2)) found = false;
if(found) return v;
for(auto& [u,w]: AL[v])
{
if(u==p) continue;
if(removed[u]) continue;
ll r = findCentroid(u,v,n);
if(r!=-1) return r;
}
return -1;
}
// saves the depth at which was found
// the minimum depth and the second minimum
ll found[MXK+1];
void gather(ll v, ll p, ll d, ll s)
{
if(s>K) return;
if(found[s]==-1) found[s] = d;
else found[s] = min(found[s],d);
for(auto& [u,w]: AL[v])
{
if(u==p) continue;
if(removed[u]) continue;
gather(u,v,d+1,s+w);
}
}
ll check(ll v, ll p, ll d, ll s)
{
if(s>K) return -1;
ll o = K-s;
ll res = -1;
if(found[o]!=-1) res = found[o]+d;
for(auto& [u,w]: AL[v])
{
if(u==p) continue;
if(removed[u]) continue;
ll r = check(u,v,d+1,s+w);
if(r!=-1)
{
if(res!=-1) res = min(res,r);
else res = r;
}
}
return res;
}
void clear(ll v, ll p, ll s)
{
if(s>K) return;
found[s] = -1;
for(auto& [u,w]: AL[v])
{
if(u==p) continue;
if(removed[u]) continue;
clear(u,v,s+w);
}
}
// returns -1 or minimum highways
// such that v is included in the path
ll process(ll v)
{
ll res = -1;
for(auto& [u,w]: AL[v])
{
if(removed[u]) continue;
found[0]=0;
ll r = check(u,v,1,w);
if(r!=-1)
{
if(res!=-1) res = min(res,r);
else res = r;
}
gather(u,v,1,w);
}
clear(v,v,0);
return res;
}
// returns -1 or minimum highways
// in the whole connected component
// divide and conquer
ll DACE(ll v)
{
ll sz = getSize(v,v);
ll c = findCentroid(v,v,sz);
ll res = process(c);
removed[c] = 1;
for(auto& [u,w]: AL[c])
{
if(removed[u]) continue;
ll res_u = DACE(u);
if(res_u!=-1){
if(res==-1) res=res_u;
else res=min(res, res_u);
}
}
return res;
}
int best_path(int n, int k, int H[][2], int L[])
{
N = n,K = k;
for(ll i=1;i<=K;i++) found[i]=-1;
for(ll i=0;i<N-1;i++)
{
ll a=H[i][0],b=H[i][1],w=L[i];
AL[a].emplace_back(b,w);
AL[b].emplace_back(a,w);
}
return DACE(0);
}
Compilation message
race.cpp: In function 'll getSize(ll, ll)':
race.cpp:22:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
22 | for(auto& [u,w]: AL[v])
| ^
race.cpp: In function 'll findCentroid(ll, ll, ll)':
race.cpp:38:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
38 | for(auto& [u,w]: AL[v])
| ^
race.cpp:51:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
51 | for(auto& [u,w]: AL[v])
| ^
race.cpp: In function 'void gather(ll, ll, ll, ll)':
race.cpp:70:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
70 | for(auto& [u,w]: AL[v])
| ^
race.cpp: In function 'll check(ll, ll, ll, ll)':
race.cpp:84:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
84 | for(auto& [u,w]: AL[v])
| ^
race.cpp: In function 'void clear(ll, ll, ll)':
race.cpp:102:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
102 | for(auto& [u,w]: AL[v])
| ^
race.cpp: In function 'll process(ll)':
race.cpp:115:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
115 | for(auto& [u,w]: AL[v])
| ^
race.cpp: In function 'll DACE(ll)':
race.cpp:142:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
142 | for(auto& [u,w]: AL[c])
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5000 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
5004 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
5004 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
5004 KB |
Output is correct |
15 |
Correct |
3 ms |
4932 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
5012 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5000 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
5004 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
5004 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
5004 KB |
Output is correct |
15 |
Correct |
3 ms |
4932 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
5012 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
4 ms |
5076 KB |
Output is correct |
22 |
Correct |
5 ms |
8660 KB |
Output is correct |
23 |
Correct |
4 ms |
8020 KB |
Output is correct |
24 |
Correct |
4 ms |
8404 KB |
Output is correct |
25 |
Correct |
5 ms |
8276 KB |
Output is correct |
26 |
Correct |
4 ms |
6428 KB |
Output is correct |
27 |
Correct |
4 ms |
8148 KB |
Output is correct |
28 |
Correct |
4 ms |
5844 KB |
Output is correct |
29 |
Correct |
4 ms |
6356 KB |
Output is correct |
30 |
Correct |
4 ms |
6484 KB |
Output is correct |
31 |
Correct |
5 ms |
7660 KB |
Output is correct |
32 |
Correct |
5 ms |
7764 KB |
Output is correct |
33 |
Correct |
5 ms |
8148 KB |
Output is correct |
34 |
Correct |
4 ms |
7324 KB |
Output is correct |
35 |
Correct |
5 ms |
8216 KB |
Output is correct |
36 |
Correct |
7 ms |
8660 KB |
Output is correct |
37 |
Correct |
5 ms |
8148 KB |
Output is correct |
38 |
Correct |
4 ms |
6996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5000 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
5004 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
5004 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
5004 KB |
Output is correct |
15 |
Correct |
3 ms |
4932 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
5012 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
133 ms |
10884 KB |
Output is correct |
20 |
Correct |
133 ms |
10916 KB |
Output is correct |
21 |
Correct |
139 ms |
10908 KB |
Output is correct |
22 |
Correct |
128 ms |
11024 KB |
Output is correct |
23 |
Correct |
69 ms |
11248 KB |
Output is correct |
24 |
Correct |
52 ms |
11076 KB |
Output is correct |
25 |
Correct |
135 ms |
13356 KB |
Output is correct |
26 |
Correct |
92 ms |
15052 KB |
Output is correct |
27 |
Correct |
165 ms |
18812 KB |
Output is correct |
28 |
Correct |
242 ms |
24912 KB |
Output is correct |
29 |
Correct |
214 ms |
24428 KB |
Output is correct |
30 |
Correct |
170 ms |
18892 KB |
Output is correct |
31 |
Correct |
178 ms |
18768 KB |
Output is correct |
32 |
Correct |
185 ms |
18860 KB |
Output is correct |
33 |
Correct |
220 ms |
17556 KB |
Output is correct |
34 |
Correct |
168 ms |
18476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5000 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
5004 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
5004 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
5004 KB |
Output is correct |
15 |
Correct |
3 ms |
4932 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
5012 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
4 ms |
5076 KB |
Output is correct |
22 |
Correct |
5 ms |
8660 KB |
Output is correct |
23 |
Correct |
4 ms |
8020 KB |
Output is correct |
24 |
Correct |
4 ms |
8404 KB |
Output is correct |
25 |
Correct |
5 ms |
8276 KB |
Output is correct |
26 |
Correct |
4 ms |
6428 KB |
Output is correct |
27 |
Correct |
4 ms |
8148 KB |
Output is correct |
28 |
Correct |
4 ms |
5844 KB |
Output is correct |
29 |
Correct |
4 ms |
6356 KB |
Output is correct |
30 |
Correct |
4 ms |
6484 KB |
Output is correct |
31 |
Correct |
5 ms |
7660 KB |
Output is correct |
32 |
Correct |
5 ms |
7764 KB |
Output is correct |
33 |
Correct |
5 ms |
8148 KB |
Output is correct |
34 |
Correct |
4 ms |
7324 KB |
Output is correct |
35 |
Correct |
5 ms |
8216 KB |
Output is correct |
36 |
Correct |
7 ms |
8660 KB |
Output is correct |
37 |
Correct |
5 ms |
8148 KB |
Output is correct |
38 |
Correct |
4 ms |
6996 KB |
Output is correct |
39 |
Correct |
133 ms |
10884 KB |
Output is correct |
40 |
Correct |
133 ms |
10916 KB |
Output is correct |
41 |
Correct |
139 ms |
10908 KB |
Output is correct |
42 |
Correct |
128 ms |
11024 KB |
Output is correct |
43 |
Correct |
69 ms |
11248 KB |
Output is correct |
44 |
Correct |
52 ms |
11076 KB |
Output is correct |
45 |
Correct |
135 ms |
13356 KB |
Output is correct |
46 |
Correct |
92 ms |
15052 KB |
Output is correct |
47 |
Correct |
165 ms |
18812 KB |
Output is correct |
48 |
Correct |
242 ms |
24912 KB |
Output is correct |
49 |
Correct |
214 ms |
24428 KB |
Output is correct |
50 |
Correct |
170 ms |
18892 KB |
Output is correct |
51 |
Correct |
178 ms |
18768 KB |
Output is correct |
52 |
Correct |
185 ms |
18860 KB |
Output is correct |
53 |
Correct |
220 ms |
17556 KB |
Output is correct |
54 |
Correct |
168 ms |
18476 KB |
Output is correct |
55 |
Correct |
10 ms |
5724 KB |
Output is correct |
56 |
Correct |
15 ms |
5588 KB |
Output is correct |
57 |
Correct |
77 ms |
11892 KB |
Output is correct |
58 |
Correct |
33 ms |
11564 KB |
Output is correct |
59 |
Correct |
96 ms |
15728 KB |
Output is correct |
60 |
Correct |
416 ms |
29228 KB |
Output is correct |
61 |
Correct |
186 ms |
18940 KB |
Output is correct |
62 |
Correct |
199 ms |
22772 KB |
Output is correct |
63 |
Correct |
286 ms |
22708 KB |
Output is correct |
64 |
Correct |
499 ms |
21140 KB |
Output is correct |
65 |
Correct |
208 ms |
19628 KB |
Output is correct |
66 |
Correct |
324 ms |
27188 KB |
Output is correct |
67 |
Correct |
106 ms |
23380 KB |
Output is correct |
68 |
Correct |
258 ms |
23500 KB |
Output is correct |
69 |
Correct |
248 ms |
23628 KB |
Output is correct |
70 |
Correct |
225 ms |
22972 KB |
Output is correct |