# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1065673 |
2024-08-19T10:43:45 Z |
Hugo1729 |
Race (IOI11_race) |
C++17 |
|
3000 ms |
21628 KB |
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
vector<pair<ll,ll>> adj[200001];
ll sz[200001];
bool marked[200001]={0};
ll k;
ll dfs_sizes(ll v, ll pV){
sz[v]=0;
for(auto [w,d] : adj[v]){
if(w!=pV&&!marked[w]){
sz[v]+=dfs_sizes(w,v);
}
}
return sz[v];
}
ll dfs_centroid(ll v, ll pV, ll subtree_sz){
for(auto [w,d] : adj[v]){
if(pV!=w&&!marked[w]&&sz[w]>=(subtree_sz/2)){
return dfs_centroid(w,v,subtree_sz);
}
}
return v;
}
void dfs_paths(ll v, ll pV,ll dist,ll l, vector<pair<ll,ll>> &a){
for(auto [w,d] : adj[v]){
if(w!=pV&&!marked[w]){
if(dist+d<=k){
a.push_back({dist+d,l+1});
dfs_paths(w,v,dist+d,l+1,a);
}
}
}
}
ll centroid_decomposition(ll v){
ll c = dfs_centroid(v,v,dfs_sizes(v,v));
marked[c]=1;
ll ans=1000001;
unordered_map<ll,ll> m;
m[0]=0;
vector<pair<ll,ll>> a;
for(auto [w,d] : adj[c]){
if(!marked[w]){
dfs_paths(w,c,d,1,a);
for(auto [dist,l] : a){
if(m.count(k-dist)){
ans=min(ans,l+m[k-dist]);
}
}
for(auto [dist,l] : a){
if(m.count(dist))m[dist]=min(m[dist],l);
else m[dist]=l;
}
a.clear();
}
}
m.clear();
a.clear();
for(auto [w,d] : adj[c]){
if(!marked[w]){
ans = min(ans,centroid_decomposition(w));
}
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[]){
for(ll i=0;i<N-1;i++){
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
k=K;
ll ans = centroid_decomposition(0);
return (ans==1000001?-1:ans);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5208 KB |
Output is correct |
2 |
Correct |
2 ms |
5212 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
5260 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
4 ms |
5136 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
3 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
5212 KB |
Output is correct |
10 |
Correct |
2 ms |
4956 KB |
Output is correct |
11 |
Correct |
3 ms |
4956 KB |
Output is correct |
12 |
Correct |
2 ms |
4956 KB |
Output is correct |
13 |
Correct |
2 ms |
5212 KB |
Output is correct |
14 |
Correct |
3 ms |
5212 KB |
Output is correct |
15 |
Correct |
2 ms |
5212 KB |
Output is correct |
16 |
Correct |
2 ms |
5212 KB |
Output is correct |
17 |
Correct |
2 ms |
5212 KB |
Output is correct |
18 |
Correct |
3 ms |
5212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5208 KB |
Output is correct |
2 |
Correct |
2 ms |
5212 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
5260 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
4 ms |
5136 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
3 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
5212 KB |
Output is correct |
10 |
Correct |
2 ms |
4956 KB |
Output is correct |
11 |
Correct |
3 ms |
4956 KB |
Output is correct |
12 |
Correct |
2 ms |
4956 KB |
Output is correct |
13 |
Correct |
2 ms |
5212 KB |
Output is correct |
14 |
Correct |
3 ms |
5212 KB |
Output is correct |
15 |
Correct |
2 ms |
5212 KB |
Output is correct |
16 |
Correct |
2 ms |
5212 KB |
Output is correct |
17 |
Correct |
2 ms |
5212 KB |
Output is correct |
18 |
Correct |
3 ms |
5212 KB |
Output is correct |
19 |
Correct |
3 ms |
4956 KB |
Output is correct |
20 |
Correct |
2 ms |
5192 KB |
Output is correct |
21 |
Correct |
39 ms |
19288 KB |
Output is correct |
22 |
Correct |
7 ms |
5468 KB |
Output is correct |
23 |
Correct |
6 ms |
5468 KB |
Output is correct |
24 |
Correct |
6 ms |
5536 KB |
Output is correct |
25 |
Correct |
60 ms |
20944 KB |
Output is correct |
26 |
Correct |
6 ms |
5536 KB |
Output is correct |
27 |
Correct |
6 ms |
5404 KB |
Output is correct |
28 |
Correct |
15 ms |
8284 KB |
Output is correct |
29 |
Correct |
30 ms |
12892 KB |
Output is correct |
30 |
Correct |
32 ms |
13908 KB |
Output is correct |
31 |
Correct |
52 ms |
20048 KB |
Output is correct |
32 |
Correct |
53 ms |
20736 KB |
Output is correct |
33 |
Correct |
40 ms |
16464 KB |
Output is correct |
34 |
Correct |
10 ms |
6104 KB |
Output is correct |
35 |
Correct |
11 ms |
6428 KB |
Output is correct |
36 |
Correct |
9 ms |
6492 KB |
Output is correct |
37 |
Correct |
39 ms |
16360 KB |
Output is correct |
38 |
Correct |
49 ms |
18968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5208 KB |
Output is correct |
2 |
Correct |
2 ms |
5212 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
5260 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
4 ms |
5136 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
3 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
5212 KB |
Output is correct |
10 |
Correct |
2 ms |
4956 KB |
Output is correct |
11 |
Correct |
3 ms |
4956 KB |
Output is correct |
12 |
Correct |
2 ms |
4956 KB |
Output is correct |
13 |
Correct |
2 ms |
5212 KB |
Output is correct |
14 |
Correct |
3 ms |
5212 KB |
Output is correct |
15 |
Correct |
2 ms |
5212 KB |
Output is correct |
16 |
Correct |
2 ms |
5212 KB |
Output is correct |
17 |
Correct |
2 ms |
5212 KB |
Output is correct |
18 |
Correct |
3 ms |
5212 KB |
Output is correct |
19 |
Execution timed out |
3067 ms |
21628 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5208 KB |
Output is correct |
2 |
Correct |
2 ms |
5212 KB |
Output is correct |
3 |
Correct |
2 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
5260 KB |
Output is correct |
5 |
Correct |
2 ms |
4956 KB |
Output is correct |
6 |
Correct |
4 ms |
5136 KB |
Output is correct |
7 |
Correct |
2 ms |
4956 KB |
Output is correct |
8 |
Correct |
3 ms |
4956 KB |
Output is correct |
9 |
Correct |
2 ms |
5212 KB |
Output is correct |
10 |
Correct |
2 ms |
4956 KB |
Output is correct |
11 |
Correct |
3 ms |
4956 KB |
Output is correct |
12 |
Correct |
2 ms |
4956 KB |
Output is correct |
13 |
Correct |
2 ms |
5212 KB |
Output is correct |
14 |
Correct |
3 ms |
5212 KB |
Output is correct |
15 |
Correct |
2 ms |
5212 KB |
Output is correct |
16 |
Correct |
2 ms |
5212 KB |
Output is correct |
17 |
Correct |
2 ms |
5212 KB |
Output is correct |
18 |
Correct |
3 ms |
5212 KB |
Output is correct |
19 |
Correct |
3 ms |
4956 KB |
Output is correct |
20 |
Correct |
2 ms |
5192 KB |
Output is correct |
21 |
Correct |
39 ms |
19288 KB |
Output is correct |
22 |
Correct |
7 ms |
5468 KB |
Output is correct |
23 |
Correct |
6 ms |
5468 KB |
Output is correct |
24 |
Correct |
6 ms |
5536 KB |
Output is correct |
25 |
Correct |
60 ms |
20944 KB |
Output is correct |
26 |
Correct |
6 ms |
5536 KB |
Output is correct |
27 |
Correct |
6 ms |
5404 KB |
Output is correct |
28 |
Correct |
15 ms |
8284 KB |
Output is correct |
29 |
Correct |
30 ms |
12892 KB |
Output is correct |
30 |
Correct |
32 ms |
13908 KB |
Output is correct |
31 |
Correct |
52 ms |
20048 KB |
Output is correct |
32 |
Correct |
53 ms |
20736 KB |
Output is correct |
33 |
Correct |
40 ms |
16464 KB |
Output is correct |
34 |
Correct |
10 ms |
6104 KB |
Output is correct |
35 |
Correct |
11 ms |
6428 KB |
Output is correct |
36 |
Correct |
9 ms |
6492 KB |
Output is correct |
37 |
Correct |
39 ms |
16360 KB |
Output is correct |
38 |
Correct |
49 ms |
18968 KB |
Output is correct |
39 |
Execution timed out |
3067 ms |
21628 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |