# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
997661 |
2024-06-12T16:40:20 Z |
blacktulip |
Race (IOI11_race) |
C++17 |
|
308 ms |
51800 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
#define _ << " " <<
const int li = 1000005;
vector<pair<int,int>> v[li];
int k;
int sub[li],cnt[li],vis[li];
int cev=0,siz;
inline void dfs(int node,int ata){
sub[node]=1;
for(auto go:v[node]){
if(go.fi==ata)continue;
if(vis[go.fi])continue;
dfs(go.fi,node);
sub[node]+=sub[go.fi];
}
}
inline int find_centroid(int node,int ata){
for(auto go:v[node]){
if(go.fi==ata)continue;
if(vis[go.fi])continue;
if(sub[go.fi]>=siz/2)return find_centroid(go.fi,node);
}
return node;
}
inline void calc(int node,int ata,int dep,int say){
if(dep>k)return ;
cev=min(cev,cnt[k-dep]+say);
//~ cout<<dep<<" () "<<say<<" :: "<<cnt[k-dep]<<" :: "<<cnt[dep]<<endl;
for(auto go:v[node]){
if(go.fi==ata)continue;
if(vis[go.fi])continue;
calc(go.fi,node,dep+go.se,say+1);
}
}
inline void increase(int node,int ata,int dep,int val){
if(dep>k)return ;
if(val>=1000000000)cnt[dep]=1000000000;
else cnt[dep]=min(1000000000,min(cnt[dep],val));
for(auto go:v[node]){
if(go.fi==ata)continue;
if(vis[go.fi])continue;
increase(go.fi,node,dep+go.se,val+1);
}
}
inline void solve(int c){
dfs(c,-1);
siz=sub[c];
c=find_centroid(c,-1);//artik c centroid
//~ cout<<c<<" () "<<cev<<endl;
vis[c]=1;
cnt[0]=0;
for(auto go:v[c]){
if(vis[go.fi])continue;
calc(go.fi,c,go.se,1);
increase(go.fi,c,go.se,1);
}
for(auto go:v[c]){
if(vis[go.fi])continue;
increase(go.fi,c,go.se,1000000000);
}
for(auto go:v[c]){
if(vis[go.fi])continue;
solve(go.fi);
}
}
int best_path(int n, int K, int h[][2], int l[]){
k=K;
for(int i=0;i<=k;i++)cnt[i]=1000000000;
for(int i=0;i<n-1;i++){
v[h[i][0]].pb({h[i][1],l[i]});
v[h[i][1]].pb({h[i][0],l[i]});
}
cev=1000000000;
solve(0);
if(cev==1000000000)cev=-1;
return cev;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
33116 KB |
Output is correct |
2 |
Correct |
5 ms |
33160 KB |
Output is correct |
3 |
Correct |
6 ms |
33116 KB |
Output is correct |
4 |
Correct |
5 ms |
32972 KB |
Output is correct |
5 |
Correct |
5 ms |
33116 KB |
Output is correct |
6 |
Correct |
5 ms |
32988 KB |
Output is correct |
7 |
Correct |
5 ms |
33116 KB |
Output is correct |
8 |
Correct |
5 ms |
33116 KB |
Output is correct |
9 |
Correct |
5 ms |
32988 KB |
Output is correct |
10 |
Correct |
4 ms |
33116 KB |
Output is correct |
11 |
Correct |
6 ms |
33112 KB |
Output is correct |
12 |
Correct |
5 ms |
33116 KB |
Output is correct |
13 |
Correct |
5 ms |
33116 KB |
Output is correct |
14 |
Correct |
5 ms |
33116 KB |
Output is correct |
15 |
Correct |
5 ms |
33144 KB |
Output is correct |
16 |
Correct |
5 ms |
33116 KB |
Output is correct |
17 |
Correct |
6 ms |
33116 KB |
Output is correct |
18 |
Correct |
5 ms |
33116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
33116 KB |
Output is correct |
2 |
Correct |
5 ms |
33160 KB |
Output is correct |
3 |
Correct |
6 ms |
33116 KB |
Output is correct |
4 |
Correct |
5 ms |
32972 KB |
Output is correct |
5 |
Correct |
5 ms |
33116 KB |
Output is correct |
6 |
Correct |
5 ms |
32988 KB |
Output is correct |
7 |
Correct |
5 ms |
33116 KB |
Output is correct |
8 |
Correct |
5 ms |
33116 KB |
Output is correct |
9 |
Correct |
5 ms |
32988 KB |
Output is correct |
10 |
Correct |
4 ms |
33116 KB |
Output is correct |
11 |
Correct |
6 ms |
33112 KB |
Output is correct |
12 |
Correct |
5 ms |
33116 KB |
Output is correct |
13 |
Correct |
5 ms |
33116 KB |
Output is correct |
14 |
Correct |
5 ms |
33116 KB |
Output is correct |
15 |
Correct |
5 ms |
33144 KB |
Output is correct |
16 |
Correct |
5 ms |
33116 KB |
Output is correct |
17 |
Correct |
6 ms |
33116 KB |
Output is correct |
18 |
Correct |
5 ms |
33116 KB |
Output is correct |
19 |
Correct |
6 ms |
33112 KB |
Output is correct |
20 |
Correct |
5 ms |
33156 KB |
Output is correct |
21 |
Correct |
7 ms |
33112 KB |
Output is correct |
22 |
Correct |
8 ms |
35036 KB |
Output is correct |
23 |
Correct |
6 ms |
35164 KB |
Output is correct |
24 |
Correct |
6 ms |
35200 KB |
Output is correct |
25 |
Correct |
6 ms |
35164 KB |
Output is correct |
26 |
Correct |
6 ms |
35164 KB |
Output is correct |
27 |
Correct |
6 ms |
35244 KB |
Output is correct |
28 |
Correct |
6 ms |
35160 KB |
Output is correct |
29 |
Correct |
6 ms |
35196 KB |
Output is correct |
30 |
Correct |
6 ms |
35164 KB |
Output is correct |
31 |
Correct |
6 ms |
35164 KB |
Output is correct |
32 |
Correct |
7 ms |
35164 KB |
Output is correct |
33 |
Correct |
6 ms |
35164 KB |
Output is correct |
34 |
Correct |
6 ms |
35164 KB |
Output is correct |
35 |
Correct |
6 ms |
35164 KB |
Output is correct |
36 |
Correct |
6 ms |
35164 KB |
Output is correct |
37 |
Correct |
6 ms |
35164 KB |
Output is correct |
38 |
Correct |
6 ms |
35164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
33116 KB |
Output is correct |
2 |
Correct |
5 ms |
33160 KB |
Output is correct |
3 |
Correct |
6 ms |
33116 KB |
Output is correct |
4 |
Correct |
5 ms |
32972 KB |
Output is correct |
5 |
Correct |
5 ms |
33116 KB |
Output is correct |
6 |
Correct |
5 ms |
32988 KB |
Output is correct |
7 |
Correct |
5 ms |
33116 KB |
Output is correct |
8 |
Correct |
5 ms |
33116 KB |
Output is correct |
9 |
Correct |
5 ms |
32988 KB |
Output is correct |
10 |
Correct |
4 ms |
33116 KB |
Output is correct |
11 |
Correct |
6 ms |
33112 KB |
Output is correct |
12 |
Correct |
5 ms |
33116 KB |
Output is correct |
13 |
Correct |
5 ms |
33116 KB |
Output is correct |
14 |
Correct |
5 ms |
33116 KB |
Output is correct |
15 |
Correct |
5 ms |
33144 KB |
Output is correct |
16 |
Correct |
5 ms |
33116 KB |
Output is correct |
17 |
Correct |
6 ms |
33116 KB |
Output is correct |
18 |
Correct |
5 ms |
33116 KB |
Output is correct |
19 |
Correct |
85 ms |
39140 KB |
Output is correct |
20 |
Correct |
86 ms |
40016 KB |
Output is correct |
21 |
Correct |
91 ms |
39764 KB |
Output is correct |
22 |
Correct |
84 ms |
40444 KB |
Output is correct |
23 |
Correct |
46 ms |
40540 KB |
Output is correct |
24 |
Correct |
36 ms |
40284 KB |
Output is correct |
25 |
Correct |
85 ms |
41300 KB |
Output is correct |
26 |
Correct |
70 ms |
42252 KB |
Output is correct |
27 |
Correct |
99 ms |
44624 KB |
Output is correct |
28 |
Correct |
136 ms |
49852 KB |
Output is correct |
29 |
Correct |
132 ms |
49536 KB |
Output is correct |
30 |
Correct |
105 ms |
45136 KB |
Output is correct |
31 |
Correct |
100 ms |
45396 KB |
Output is correct |
32 |
Correct |
112 ms |
45056 KB |
Output is correct |
33 |
Correct |
120 ms |
44116 KB |
Output is correct |
34 |
Correct |
133 ms |
44456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
33116 KB |
Output is correct |
2 |
Correct |
5 ms |
33160 KB |
Output is correct |
3 |
Correct |
6 ms |
33116 KB |
Output is correct |
4 |
Correct |
5 ms |
32972 KB |
Output is correct |
5 |
Correct |
5 ms |
33116 KB |
Output is correct |
6 |
Correct |
5 ms |
32988 KB |
Output is correct |
7 |
Correct |
5 ms |
33116 KB |
Output is correct |
8 |
Correct |
5 ms |
33116 KB |
Output is correct |
9 |
Correct |
5 ms |
32988 KB |
Output is correct |
10 |
Correct |
4 ms |
33116 KB |
Output is correct |
11 |
Correct |
6 ms |
33112 KB |
Output is correct |
12 |
Correct |
5 ms |
33116 KB |
Output is correct |
13 |
Correct |
5 ms |
33116 KB |
Output is correct |
14 |
Correct |
5 ms |
33116 KB |
Output is correct |
15 |
Correct |
5 ms |
33144 KB |
Output is correct |
16 |
Correct |
5 ms |
33116 KB |
Output is correct |
17 |
Correct |
6 ms |
33116 KB |
Output is correct |
18 |
Correct |
5 ms |
33116 KB |
Output is correct |
19 |
Correct |
6 ms |
33112 KB |
Output is correct |
20 |
Correct |
5 ms |
33156 KB |
Output is correct |
21 |
Correct |
7 ms |
33112 KB |
Output is correct |
22 |
Correct |
8 ms |
35036 KB |
Output is correct |
23 |
Correct |
6 ms |
35164 KB |
Output is correct |
24 |
Correct |
6 ms |
35200 KB |
Output is correct |
25 |
Correct |
6 ms |
35164 KB |
Output is correct |
26 |
Correct |
6 ms |
35164 KB |
Output is correct |
27 |
Correct |
6 ms |
35244 KB |
Output is correct |
28 |
Correct |
6 ms |
35160 KB |
Output is correct |
29 |
Correct |
6 ms |
35196 KB |
Output is correct |
30 |
Correct |
6 ms |
35164 KB |
Output is correct |
31 |
Correct |
6 ms |
35164 KB |
Output is correct |
32 |
Correct |
7 ms |
35164 KB |
Output is correct |
33 |
Correct |
6 ms |
35164 KB |
Output is correct |
34 |
Correct |
6 ms |
35164 KB |
Output is correct |
35 |
Correct |
6 ms |
35164 KB |
Output is correct |
36 |
Correct |
6 ms |
35164 KB |
Output is correct |
37 |
Correct |
6 ms |
35164 KB |
Output is correct |
38 |
Correct |
6 ms |
35164 KB |
Output is correct |
39 |
Correct |
85 ms |
39140 KB |
Output is correct |
40 |
Correct |
86 ms |
40016 KB |
Output is correct |
41 |
Correct |
91 ms |
39764 KB |
Output is correct |
42 |
Correct |
84 ms |
40444 KB |
Output is correct |
43 |
Correct |
46 ms |
40540 KB |
Output is correct |
44 |
Correct |
36 ms |
40284 KB |
Output is correct |
45 |
Correct |
85 ms |
41300 KB |
Output is correct |
46 |
Correct |
70 ms |
42252 KB |
Output is correct |
47 |
Correct |
99 ms |
44624 KB |
Output is correct |
48 |
Correct |
136 ms |
49852 KB |
Output is correct |
49 |
Correct |
132 ms |
49536 KB |
Output is correct |
50 |
Correct |
105 ms |
45136 KB |
Output is correct |
51 |
Correct |
100 ms |
45396 KB |
Output is correct |
52 |
Correct |
112 ms |
45056 KB |
Output is correct |
53 |
Correct |
120 ms |
44116 KB |
Output is correct |
54 |
Correct |
133 ms |
44456 KB |
Output is correct |
55 |
Correct |
13 ms |
33644 KB |
Output is correct |
56 |
Correct |
13 ms |
33372 KB |
Output is correct |
57 |
Correct |
51 ms |
39320 KB |
Output is correct |
58 |
Correct |
26 ms |
40264 KB |
Output is correct |
59 |
Correct |
70 ms |
44524 KB |
Output is correct |
60 |
Correct |
276 ms |
51800 KB |
Output is correct |
61 |
Correct |
129 ms |
44668 KB |
Output is correct |
62 |
Correct |
122 ms |
47336 KB |
Output is correct |
63 |
Correct |
151 ms |
47124 KB |
Output is correct |
64 |
Correct |
270 ms |
45972 KB |
Output is correct |
65 |
Correct |
109 ms |
46160 KB |
Output is correct |
66 |
Correct |
308 ms |
48784 KB |
Output is correct |
67 |
Correct |
71 ms |
48888 KB |
Output is correct |
68 |
Correct |
169 ms |
47444 KB |
Output is correct |
69 |
Correct |
206 ms |
45688 KB |
Output is correct |
70 |
Correct |
148 ms |
47600 KB |
Output is correct |