# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
82791 |
2018-11-01T16:40:42 Z |
vibster |
Race (IOI11_race) |
C++14 |
|
1823 ms |
158172 KB |
#include "race.h"
#include<bits/stdc++.h>
#define endl '\n'
#define INF 1e18
typedef long long int ll;
using namespace std;
const int NMAX=2e5+1, LOGN=19, NMAX2=1e6+1;
int sz[NMAX];
ll k;
vector <set<pair<int,int>>> node(NMAX);
multiset <int> dis[NMAX2];
ll ans=INF;
//Decompose
//subtree size
int dfs0(int u, int p){
sz[u]=1;
for(auto b: node[u]){
if(b.first==p)continue;
sz[u]+=dfs0(b.first, u);
}
return sz[u];
}
//find centroid
int dfs1(int u, int p, int n){
for(auto b:node[u]){
if(b.first==p)continue;
if(sz[b.first]>n/2)return dfs1(b.first, u, n);
}
return u;
}
//updating dist multiset
void dfs2(int u, int p, ll dista, int len, bool s){
if(dista<=k)
if(s)dis[dista].insert(len);
else if(dis[dista].find(len)!=dis[dista].end())dis[dista].erase(dis[dista].find(len));
for(auto b:node[u]){
if(b.first==p)continue;
dfs2(b.first,u,dista+b.second, len+1,s);
}
}
//upading ans
void dfs3(int u, int p, ll dista, int len){
if((ll)k-dista>=0 && !dis[k-dista].empty())ans=min(ans,(ll) (*dis[k-dista].begin())+len);
for(auto b:node[u]){
if(b.first==p)continue;
dfs3(b.first, u, dista+b.second, len+1);
}
}
//Decompose
void Decompose(int u, int p){
int n=dfs0(u,p);
int centroid=dfs1(u,p,n);
dfs2(centroid, p, 0, 0, 1);
for(auto b:node[centroid]){
if(b.first==p)continue;
dfs2(b.first,centroid,b.second,1,0);
dfs3(b.first,centroid,b.second,1);
}
for(auto b:node[centroid]){
if(b.first==p)continue;
node[b.first].erase({centroid,b.second});
Decompose(b.first, centroid);
}
node[centroid].clear();
}
int best_path(int N, int K, int H[][2], int L[]){
k=K;
for(int i=0; i<N-1; i++){
node[H[i][0]].insert({H[i][1],L[i]});
node[H[i][1]].insert({H[i][0],L[i]});
}
Decompose(0,-1);
if(ans>=INF)return -1;
else return ans;
}
Compilation message
race.cpp: In function 'void dfs2(int, int, ll, int, bool)':
race.cpp:37:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if(dista<=k)
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
56696 KB |
Output is correct |
2 |
Correct |
53 ms |
56848 KB |
Output is correct |
3 |
Correct |
53 ms |
56848 KB |
Output is correct |
4 |
Correct |
55 ms |
56848 KB |
Output is correct |
5 |
Correct |
56 ms |
56848 KB |
Output is correct |
6 |
Correct |
53 ms |
56848 KB |
Output is correct |
7 |
Correct |
52 ms |
56848 KB |
Output is correct |
8 |
Correct |
55 ms |
56848 KB |
Output is correct |
9 |
Correct |
54 ms |
56848 KB |
Output is correct |
10 |
Correct |
50 ms |
56848 KB |
Output is correct |
11 |
Correct |
54 ms |
56860 KB |
Output is correct |
12 |
Correct |
52 ms |
56920 KB |
Output is correct |
13 |
Correct |
52 ms |
56956 KB |
Output is correct |
14 |
Correct |
57 ms |
57016 KB |
Output is correct |
15 |
Correct |
58 ms |
57016 KB |
Output is correct |
16 |
Correct |
56 ms |
57068 KB |
Output is correct |
17 |
Correct |
58 ms |
57068 KB |
Output is correct |
18 |
Correct |
54 ms |
57108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
56696 KB |
Output is correct |
2 |
Correct |
53 ms |
56848 KB |
Output is correct |
3 |
Correct |
53 ms |
56848 KB |
Output is correct |
4 |
Correct |
55 ms |
56848 KB |
Output is correct |
5 |
Correct |
56 ms |
56848 KB |
Output is correct |
6 |
Correct |
53 ms |
56848 KB |
Output is correct |
7 |
Correct |
52 ms |
56848 KB |
Output is correct |
8 |
Correct |
55 ms |
56848 KB |
Output is correct |
9 |
Correct |
54 ms |
56848 KB |
Output is correct |
10 |
Correct |
50 ms |
56848 KB |
Output is correct |
11 |
Correct |
54 ms |
56860 KB |
Output is correct |
12 |
Correct |
52 ms |
56920 KB |
Output is correct |
13 |
Correct |
52 ms |
56956 KB |
Output is correct |
14 |
Correct |
57 ms |
57016 KB |
Output is correct |
15 |
Correct |
58 ms |
57016 KB |
Output is correct |
16 |
Correct |
56 ms |
57068 KB |
Output is correct |
17 |
Correct |
58 ms |
57068 KB |
Output is correct |
18 |
Correct |
54 ms |
57108 KB |
Output is correct |
19 |
Correct |
53 ms |
57108 KB |
Output is correct |
20 |
Correct |
58 ms |
57116 KB |
Output is correct |
21 |
Correct |
56 ms |
57136 KB |
Output is correct |
22 |
Correct |
56 ms |
57148 KB |
Output is correct |
23 |
Correct |
57 ms |
57164 KB |
Output is correct |
24 |
Correct |
58 ms |
57180 KB |
Output is correct |
25 |
Correct |
57 ms |
57196 KB |
Output is correct |
26 |
Correct |
58 ms |
57240 KB |
Output is correct |
27 |
Correct |
56 ms |
57268 KB |
Output is correct |
28 |
Correct |
56 ms |
57268 KB |
Output is correct |
29 |
Correct |
57 ms |
57272 KB |
Output is correct |
30 |
Correct |
59 ms |
57416 KB |
Output is correct |
31 |
Correct |
57 ms |
57416 KB |
Output is correct |
32 |
Correct |
56 ms |
57416 KB |
Output is correct |
33 |
Correct |
58 ms |
57416 KB |
Output is correct |
34 |
Correct |
56 ms |
57416 KB |
Output is correct |
35 |
Correct |
55 ms |
57416 KB |
Output is correct |
36 |
Correct |
56 ms |
57416 KB |
Output is correct |
37 |
Correct |
58 ms |
57416 KB |
Output is correct |
38 |
Correct |
59 ms |
57456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
56696 KB |
Output is correct |
2 |
Correct |
53 ms |
56848 KB |
Output is correct |
3 |
Correct |
53 ms |
56848 KB |
Output is correct |
4 |
Correct |
55 ms |
56848 KB |
Output is correct |
5 |
Correct |
56 ms |
56848 KB |
Output is correct |
6 |
Correct |
53 ms |
56848 KB |
Output is correct |
7 |
Correct |
52 ms |
56848 KB |
Output is correct |
8 |
Correct |
55 ms |
56848 KB |
Output is correct |
9 |
Correct |
54 ms |
56848 KB |
Output is correct |
10 |
Correct |
50 ms |
56848 KB |
Output is correct |
11 |
Correct |
54 ms |
56860 KB |
Output is correct |
12 |
Correct |
52 ms |
56920 KB |
Output is correct |
13 |
Correct |
52 ms |
56956 KB |
Output is correct |
14 |
Correct |
57 ms |
57016 KB |
Output is correct |
15 |
Correct |
58 ms |
57016 KB |
Output is correct |
16 |
Correct |
56 ms |
57068 KB |
Output is correct |
17 |
Correct |
58 ms |
57068 KB |
Output is correct |
18 |
Correct |
54 ms |
57108 KB |
Output is correct |
19 |
Correct |
649 ms |
70184 KB |
Output is correct |
20 |
Correct |
655 ms |
71328 KB |
Output is correct |
21 |
Correct |
789 ms |
73960 KB |
Output is correct |
22 |
Correct |
696 ms |
77560 KB |
Output is correct |
23 |
Correct |
478 ms |
77560 KB |
Output is correct |
24 |
Correct |
348 ms |
77560 KB |
Output is correct |
25 |
Correct |
683 ms |
81868 KB |
Output is correct |
26 |
Correct |
695 ms |
88596 KB |
Output is correct |
27 |
Correct |
759 ms |
93400 KB |
Output is correct |
28 |
Correct |
1362 ms |
105656 KB |
Output is correct |
29 |
Correct |
1367 ms |
108100 KB |
Output is correct |
30 |
Correct |
711 ms |
108100 KB |
Output is correct |
31 |
Correct |
700 ms |
108100 KB |
Output is correct |
32 |
Correct |
876 ms |
108228 KB |
Output is correct |
33 |
Correct |
1098 ms |
111156 KB |
Output is correct |
34 |
Correct |
1002 ms |
114932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
56696 KB |
Output is correct |
2 |
Correct |
53 ms |
56848 KB |
Output is correct |
3 |
Correct |
53 ms |
56848 KB |
Output is correct |
4 |
Correct |
55 ms |
56848 KB |
Output is correct |
5 |
Correct |
56 ms |
56848 KB |
Output is correct |
6 |
Correct |
53 ms |
56848 KB |
Output is correct |
7 |
Correct |
52 ms |
56848 KB |
Output is correct |
8 |
Correct |
55 ms |
56848 KB |
Output is correct |
9 |
Correct |
54 ms |
56848 KB |
Output is correct |
10 |
Correct |
50 ms |
56848 KB |
Output is correct |
11 |
Correct |
54 ms |
56860 KB |
Output is correct |
12 |
Correct |
52 ms |
56920 KB |
Output is correct |
13 |
Correct |
52 ms |
56956 KB |
Output is correct |
14 |
Correct |
57 ms |
57016 KB |
Output is correct |
15 |
Correct |
58 ms |
57016 KB |
Output is correct |
16 |
Correct |
56 ms |
57068 KB |
Output is correct |
17 |
Correct |
58 ms |
57068 KB |
Output is correct |
18 |
Correct |
54 ms |
57108 KB |
Output is correct |
19 |
Correct |
53 ms |
57108 KB |
Output is correct |
20 |
Correct |
58 ms |
57116 KB |
Output is correct |
21 |
Correct |
56 ms |
57136 KB |
Output is correct |
22 |
Correct |
56 ms |
57148 KB |
Output is correct |
23 |
Correct |
57 ms |
57164 KB |
Output is correct |
24 |
Correct |
58 ms |
57180 KB |
Output is correct |
25 |
Correct |
57 ms |
57196 KB |
Output is correct |
26 |
Correct |
58 ms |
57240 KB |
Output is correct |
27 |
Correct |
56 ms |
57268 KB |
Output is correct |
28 |
Correct |
56 ms |
57268 KB |
Output is correct |
29 |
Correct |
57 ms |
57272 KB |
Output is correct |
30 |
Correct |
59 ms |
57416 KB |
Output is correct |
31 |
Correct |
57 ms |
57416 KB |
Output is correct |
32 |
Correct |
56 ms |
57416 KB |
Output is correct |
33 |
Correct |
58 ms |
57416 KB |
Output is correct |
34 |
Correct |
56 ms |
57416 KB |
Output is correct |
35 |
Correct |
55 ms |
57416 KB |
Output is correct |
36 |
Correct |
56 ms |
57416 KB |
Output is correct |
37 |
Correct |
58 ms |
57416 KB |
Output is correct |
38 |
Correct |
59 ms |
57456 KB |
Output is correct |
39 |
Correct |
649 ms |
70184 KB |
Output is correct |
40 |
Correct |
655 ms |
71328 KB |
Output is correct |
41 |
Correct |
789 ms |
73960 KB |
Output is correct |
42 |
Correct |
696 ms |
77560 KB |
Output is correct |
43 |
Correct |
478 ms |
77560 KB |
Output is correct |
44 |
Correct |
348 ms |
77560 KB |
Output is correct |
45 |
Correct |
683 ms |
81868 KB |
Output is correct |
46 |
Correct |
695 ms |
88596 KB |
Output is correct |
47 |
Correct |
759 ms |
93400 KB |
Output is correct |
48 |
Correct |
1362 ms |
105656 KB |
Output is correct |
49 |
Correct |
1367 ms |
108100 KB |
Output is correct |
50 |
Correct |
711 ms |
108100 KB |
Output is correct |
51 |
Correct |
700 ms |
108100 KB |
Output is correct |
52 |
Correct |
876 ms |
108228 KB |
Output is correct |
53 |
Correct |
1098 ms |
111156 KB |
Output is correct |
54 |
Correct |
1002 ms |
114932 KB |
Output is correct |
55 |
Correct |
82 ms |
114932 KB |
Output is correct |
56 |
Correct |
98 ms |
114932 KB |
Output is correct |
57 |
Correct |
581 ms |
114932 KB |
Output is correct |
58 |
Correct |
238 ms |
114932 KB |
Output is correct |
59 |
Correct |
361 ms |
117220 KB |
Output is correct |
60 |
Correct |
1816 ms |
140200 KB |
Output is correct |
61 |
Correct |
724 ms |
140200 KB |
Output is correct |
62 |
Correct |
830 ms |
140200 KB |
Output is correct |
63 |
Correct |
1000 ms |
140200 KB |
Output is correct |
64 |
Correct |
1823 ms |
143716 KB |
Output is correct |
65 |
Correct |
1035 ms |
143716 KB |
Output is correct |
66 |
Correct |
1738 ms |
149556 KB |
Output is correct |
67 |
Correct |
787 ms |
154300 KB |
Output is correct |
68 |
Correct |
1092 ms |
154300 KB |
Output is correct |
69 |
Correct |
1085 ms |
156072 KB |
Output is correct |
70 |
Correct |
987 ms |
158172 KB |
Output is correct |