# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
126344 |
2019-07-07T12:26:39 Z |
ksmzzang2003 |
Race (IOI11_race) |
C++14 |
|
513 ms |
34636 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> pii;
int N,K,L[200003];
int par[200003],sz[200003];
vector <pii> adj[200003];
int check[1000003];
bool del[200003];
int ans = 1987654321;
vector <pii> lazy;
vector <int> usecheck;
int dfs1(int now,int prev)
{
sz[now] =0;
for(int i=0;i<adj[now].size();i++)
{
int next = adj[now][i].first;
int cost = adj[now][i].second;
if(next == prev) continue;
if(del[next]) continue;
sz[now] += dfs1(next,now);
}
return ++sz[now];
}
int find_cen(int now,int prev,int root)
{
for(int i=0;i<adj[now].size();i++)
{
int next = adj[now][i].first;
int cost = adj[now][i].second;
if(next == prev) continue;
if(del[next]) continue;
if(sz[next]*2>sz[root]) return find_cen(next,now,root);
}
return now;
}
int dfs2(int now,int prev,int sum,int depth,int maxans=1987654321)
{
if(depth>=maxans) return 1987654321;
int ret = 1987654321;
if(sum>K) return 1987654321;
if(check[K-sum]!=1987654321) ret= min(ret,depth + check[K-sum]);
lazy.push_back(pii(sum,depth));
for(int i=0;i<adj[now].size();i++)
{
int next = adj[now][i].first;
int cost = adj[now][i].second;
if(next == prev) continue;
if(del[next]) continue;
ret = min(ret,dfs2(next,now,sum+cost,depth+1,ret));
if(sum==0)
{
for(pii it:lazy) check[it.first] = min(check[it.first],it.second),usecheck.push_back(it.first);
lazy.clear();
}
}
return ret;
}
void g(int now,int prev)
{
dfs1(now,-1);
int cen = find_cen(now,-1,now);
for(int it:usecheck) check[it] = 1987654321;
usecheck.clear();
check[0] = 0;
ans = min(ans,dfs2(cen,-1,0,0));
del[cen] = true;
for(int i=0;i<adj[cen].size();i++)
{
int next = adj[cen][i].first;
int cost = adj[cen][i].second;
if(del[next]) continue;
g(next,now);
}
}
int best_path(int n, int k, int h[][2], int l[])
{
fill(check,check+1000003,1987654321);
N= n ; K = k;
for(int i=0;i<n-1;i++)
{
adj[h[i][0]].push_back(pii(h[i][1],l[i]));
adj[h[i][1]].push_back(pii(h[i][0],l[i]));
}
g(1,-1);
return (ans>=1987654300)?-1:ans;
}
Compilation message
race.cpp: In function 'int dfs1(int, int)':
race.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[now].size();i++)
~^~~~~~~~~~~~~~~~
race.cpp:20:13: warning: unused variable 'cost' [-Wunused-variable]
int cost = adj[now][i].second;
^~~~
race.cpp: In function 'int find_cen(int, int, int)':
race.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[now].size();i++)
~^~~~~~~~~~~~~~~~
race.cpp:33:13: warning: unused variable 'cost' [-Wunused-variable]
int cost = adj[now][i].second;
^~~~
race.cpp: In function 'int dfs2(int, int, int, int, int)':
race.cpp:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[now].size();i++)
~^~~~~~~~~~~~~~~~
race.cpp: In function 'void g(int, int)':
race.cpp:73:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[cen].size();i++)
~^~~~~~~~~~~~~~~~
race.cpp:76:13: warning: unused variable 'cost' [-Wunused-variable]
int cost = adj[cen][i].second;
^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
8952 KB |
Output is correct |
3 |
Correct |
10 ms |
8952 KB |
Output is correct |
4 |
Correct |
11 ms |
9080 KB |
Output is correct |
5 |
Correct |
9 ms |
8952 KB |
Output is correct |
6 |
Correct |
9 ms |
8892 KB |
Output is correct |
7 |
Correct |
9 ms |
8952 KB |
Output is correct |
8 |
Correct |
9 ms |
8952 KB |
Output is correct |
9 |
Correct |
9 ms |
8952 KB |
Output is correct |
10 |
Correct |
9 ms |
8952 KB |
Output is correct |
11 |
Correct |
10 ms |
8952 KB |
Output is correct |
12 |
Correct |
10 ms |
8952 KB |
Output is correct |
13 |
Correct |
10 ms |
8952 KB |
Output is correct |
14 |
Correct |
9 ms |
8952 KB |
Output is correct |
15 |
Correct |
9 ms |
8952 KB |
Output is correct |
16 |
Correct |
9 ms |
8952 KB |
Output is correct |
17 |
Correct |
9 ms |
8952 KB |
Output is correct |
18 |
Correct |
9 ms |
8956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
8952 KB |
Output is correct |
3 |
Correct |
10 ms |
8952 KB |
Output is correct |
4 |
Correct |
11 ms |
9080 KB |
Output is correct |
5 |
Correct |
9 ms |
8952 KB |
Output is correct |
6 |
Correct |
9 ms |
8892 KB |
Output is correct |
7 |
Correct |
9 ms |
8952 KB |
Output is correct |
8 |
Correct |
9 ms |
8952 KB |
Output is correct |
9 |
Correct |
9 ms |
8952 KB |
Output is correct |
10 |
Correct |
9 ms |
8952 KB |
Output is correct |
11 |
Correct |
10 ms |
8952 KB |
Output is correct |
12 |
Correct |
10 ms |
8952 KB |
Output is correct |
13 |
Correct |
10 ms |
8952 KB |
Output is correct |
14 |
Correct |
9 ms |
8952 KB |
Output is correct |
15 |
Correct |
9 ms |
8952 KB |
Output is correct |
16 |
Correct |
9 ms |
8952 KB |
Output is correct |
17 |
Correct |
9 ms |
8952 KB |
Output is correct |
18 |
Correct |
9 ms |
8956 KB |
Output is correct |
19 |
Correct |
9 ms |
8952 KB |
Output is correct |
20 |
Correct |
9 ms |
8952 KB |
Output is correct |
21 |
Correct |
10 ms |
9080 KB |
Output is correct |
22 |
Correct |
10 ms |
8952 KB |
Output is correct |
23 |
Correct |
10 ms |
9080 KB |
Output is correct |
24 |
Correct |
10 ms |
8956 KB |
Output is correct |
25 |
Correct |
10 ms |
9080 KB |
Output is correct |
26 |
Correct |
10 ms |
9080 KB |
Output is correct |
27 |
Correct |
10 ms |
8956 KB |
Output is correct |
28 |
Correct |
10 ms |
9080 KB |
Output is correct |
29 |
Correct |
10 ms |
9080 KB |
Output is correct |
30 |
Correct |
10 ms |
9080 KB |
Output is correct |
31 |
Correct |
10 ms |
9080 KB |
Output is correct |
32 |
Correct |
10 ms |
8952 KB |
Output is correct |
33 |
Correct |
11 ms |
9080 KB |
Output is correct |
34 |
Correct |
10 ms |
8952 KB |
Output is correct |
35 |
Correct |
10 ms |
8952 KB |
Output is correct |
36 |
Correct |
11 ms |
9080 KB |
Output is correct |
37 |
Correct |
10 ms |
9080 KB |
Output is correct |
38 |
Correct |
10 ms |
8952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
8952 KB |
Output is correct |
3 |
Correct |
10 ms |
8952 KB |
Output is correct |
4 |
Correct |
11 ms |
9080 KB |
Output is correct |
5 |
Correct |
9 ms |
8952 KB |
Output is correct |
6 |
Correct |
9 ms |
8892 KB |
Output is correct |
7 |
Correct |
9 ms |
8952 KB |
Output is correct |
8 |
Correct |
9 ms |
8952 KB |
Output is correct |
9 |
Correct |
9 ms |
8952 KB |
Output is correct |
10 |
Correct |
9 ms |
8952 KB |
Output is correct |
11 |
Correct |
10 ms |
8952 KB |
Output is correct |
12 |
Correct |
10 ms |
8952 KB |
Output is correct |
13 |
Correct |
10 ms |
8952 KB |
Output is correct |
14 |
Correct |
9 ms |
8952 KB |
Output is correct |
15 |
Correct |
9 ms |
8952 KB |
Output is correct |
16 |
Correct |
9 ms |
8952 KB |
Output is correct |
17 |
Correct |
9 ms |
8952 KB |
Output is correct |
18 |
Correct |
9 ms |
8956 KB |
Output is correct |
19 |
Correct |
156 ms |
14668 KB |
Output is correct |
20 |
Correct |
150 ms |
14452 KB |
Output is correct |
21 |
Correct |
161 ms |
14792 KB |
Output is correct |
22 |
Correct |
152 ms |
15220 KB |
Output is correct |
23 |
Correct |
153 ms |
14456 KB |
Output is correct |
24 |
Correct |
95 ms |
14604 KB |
Output is correct |
25 |
Correct |
223 ms |
18040 KB |
Output is correct |
26 |
Correct |
128 ms |
21644 KB |
Output is correct |
27 |
Correct |
213 ms |
22780 KB |
Output is correct |
28 |
Correct |
321 ms |
30456 KB |
Output is correct |
29 |
Correct |
332 ms |
27256 KB |
Output is correct |
30 |
Correct |
213 ms |
22836 KB |
Output is correct |
31 |
Correct |
211 ms |
22804 KB |
Output is correct |
32 |
Correct |
237 ms |
22936 KB |
Output is correct |
33 |
Correct |
313 ms |
21496 KB |
Output is correct |
34 |
Correct |
281 ms |
22604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
8952 KB |
Output is correct |
3 |
Correct |
10 ms |
8952 KB |
Output is correct |
4 |
Correct |
11 ms |
9080 KB |
Output is correct |
5 |
Correct |
9 ms |
8952 KB |
Output is correct |
6 |
Correct |
9 ms |
8892 KB |
Output is correct |
7 |
Correct |
9 ms |
8952 KB |
Output is correct |
8 |
Correct |
9 ms |
8952 KB |
Output is correct |
9 |
Correct |
9 ms |
8952 KB |
Output is correct |
10 |
Correct |
9 ms |
8952 KB |
Output is correct |
11 |
Correct |
10 ms |
8952 KB |
Output is correct |
12 |
Correct |
10 ms |
8952 KB |
Output is correct |
13 |
Correct |
10 ms |
8952 KB |
Output is correct |
14 |
Correct |
9 ms |
8952 KB |
Output is correct |
15 |
Correct |
9 ms |
8952 KB |
Output is correct |
16 |
Correct |
9 ms |
8952 KB |
Output is correct |
17 |
Correct |
9 ms |
8952 KB |
Output is correct |
18 |
Correct |
9 ms |
8956 KB |
Output is correct |
19 |
Correct |
9 ms |
8952 KB |
Output is correct |
20 |
Correct |
9 ms |
8952 KB |
Output is correct |
21 |
Correct |
10 ms |
9080 KB |
Output is correct |
22 |
Correct |
10 ms |
8952 KB |
Output is correct |
23 |
Correct |
10 ms |
9080 KB |
Output is correct |
24 |
Correct |
10 ms |
8956 KB |
Output is correct |
25 |
Correct |
10 ms |
9080 KB |
Output is correct |
26 |
Correct |
10 ms |
9080 KB |
Output is correct |
27 |
Correct |
10 ms |
8956 KB |
Output is correct |
28 |
Correct |
10 ms |
9080 KB |
Output is correct |
29 |
Correct |
10 ms |
9080 KB |
Output is correct |
30 |
Correct |
10 ms |
9080 KB |
Output is correct |
31 |
Correct |
10 ms |
9080 KB |
Output is correct |
32 |
Correct |
10 ms |
8952 KB |
Output is correct |
33 |
Correct |
11 ms |
9080 KB |
Output is correct |
34 |
Correct |
10 ms |
8952 KB |
Output is correct |
35 |
Correct |
10 ms |
8952 KB |
Output is correct |
36 |
Correct |
11 ms |
9080 KB |
Output is correct |
37 |
Correct |
10 ms |
9080 KB |
Output is correct |
38 |
Correct |
10 ms |
8952 KB |
Output is correct |
39 |
Correct |
156 ms |
14668 KB |
Output is correct |
40 |
Correct |
150 ms |
14452 KB |
Output is correct |
41 |
Correct |
161 ms |
14792 KB |
Output is correct |
42 |
Correct |
152 ms |
15220 KB |
Output is correct |
43 |
Correct |
153 ms |
14456 KB |
Output is correct |
44 |
Correct |
95 ms |
14604 KB |
Output is correct |
45 |
Correct |
223 ms |
18040 KB |
Output is correct |
46 |
Correct |
128 ms |
21644 KB |
Output is correct |
47 |
Correct |
213 ms |
22780 KB |
Output is correct |
48 |
Correct |
321 ms |
30456 KB |
Output is correct |
49 |
Correct |
332 ms |
27256 KB |
Output is correct |
50 |
Correct |
213 ms |
22836 KB |
Output is correct |
51 |
Correct |
211 ms |
22804 KB |
Output is correct |
52 |
Correct |
237 ms |
22936 KB |
Output is correct |
53 |
Correct |
313 ms |
21496 KB |
Output is correct |
54 |
Correct |
281 ms |
22604 KB |
Output is correct |
55 |
Correct |
20 ms |
9720 KB |
Output is correct |
56 |
Correct |
21 ms |
9720 KB |
Output is correct |
57 |
Correct |
114 ms |
16888 KB |
Output is correct |
58 |
Correct |
55 ms |
17744 KB |
Output is correct |
59 |
Correct |
129 ms |
21616 KB |
Output is correct |
60 |
Correct |
492 ms |
34636 KB |
Output is correct |
61 |
Correct |
222 ms |
23292 KB |
Output is correct |
62 |
Correct |
245 ms |
23944 KB |
Output is correct |
63 |
Correct |
302 ms |
23812 KB |
Output is correct |
64 |
Correct |
513 ms |
25324 KB |
Output is correct |
65 |
Correct |
275 ms |
23772 KB |
Output is correct |
66 |
Correct |
483 ms |
29816 KB |
Output is correct |
67 |
Correct |
155 ms |
25376 KB |
Output is correct |
68 |
Correct |
312 ms |
24052 KB |
Output is correct |
69 |
Correct |
301 ms |
24208 KB |
Output is correct |
70 |
Correct |
281 ms |
23540 KB |
Output is correct |