# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
132998 |
2019-07-20T03:48:40 Z |
wilwxk |
Race (IOI11_race) |
C++14 |
|
1054 ms |
40464 KB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+5;
const int MAXX=1e6+5;
vector<int> g[MAXN], pes[MAXN];
int n, respf;
ll x;
class solution {
public:
int resp=MAXN;
void init() {
tam[n]=0;
memset(prof, 0, sizeof(prof));
fill(best, best+x+2, MAXN);
solve(0, 1);
}
void solve(int cur, int k) {
basic_scan(cur, cur);
cur=find_centroid(cur, cur, tam[cur]);
prof[cur]=k;
// printf(">> %d <<\n", cur);
best[0]=0;
for(int i=0; i<g[cur].size(); i++) {
int viz=g[cur][i]; ll peso=pes[cur][i];
if(prof[viz]) continue;
adv_scan(viz, cur, 1, peso, 0);
adv_scan(viz, cur, 1, peso, 1);
}
for(int i=0; i<g[cur].size(); i++) {
int viz=g[cur][i]; ll peso=pes[cur][i];
if(prof[viz]) continue;
adv_scan(viz, cur, 1, peso, -1);
}
for(auto viz : g[cur]) {
if(prof[viz]) continue;
solve(viz, k+1);
}
}
private:
int tam[MAXN], prof[MAXN];
int best[MAXX];
void basic_scan(int cur, int p) {
tam[cur]=1;
for(auto viz : g[cur]) {
if(viz==p||prof[viz]) continue;
basic_scan(viz, cur);
tam[cur]+=tam[viz];
}
}
void adv_scan(int cur, int p, int d, ll dd, int k) {
if(dd>x) return;
if(k==0) resp=min(resp, d+best[x-dd]);
else if(k==1) best[dd]=min(best[dd], d);
else best[dd]=MAXN;
for(int i=0; i<g[cur].size(); i++) {
int viz=g[cur][i]; ll peso=pes[cur][i];
if(viz==p||prof[viz]) continue;
adv_scan(viz, cur, d+1, dd+peso, k);
}
}
int find_centroid(int cur, int p, int val) {
int grande=n;
for(auto viz : g[cur]) if(viz!=p&&!prof[viz]&&tam[viz]>tam[grande]) grande=viz;
if(tam[grande]*2<=val) return cur;
return find_centroid(grande, cur, val);
}
};
int best_path(int N, int K, int H[][2], int L[])
{
n=N; x=K;
for(int i=0; i<n-1; i++) {
int a=H[i][0]; int b=H[i][1];
g[a].push_back(b); pes[a].push_back(L[i]);
g[b].push_back(a); pes[b].push_back(L[i]);
}
solution sol;
sol.init();
respf=sol.resp;
if(respf>n) respf=-1;
return respf;
}
Compilation message
race.cpp: In member function 'void solution::solve(int, int)':
race.cpp:29:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<g[cur].size(); i++) {
~^~~~~~~~~~~~~~
race.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<g[cur].size(); i++) {
~^~~~~~~~~~~~~~
race.cpp: In member function 'void solution::adv_scan(int, int, int, ll, int)':
race.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<g[cur].size(); i++) {
~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
10552 KB |
Output is correct |
2 |
Correct |
12 ms |
10532 KB |
Output is correct |
3 |
Correct |
11 ms |
10488 KB |
Output is correct |
4 |
Correct |
11 ms |
10488 KB |
Output is correct |
5 |
Correct |
11 ms |
10488 KB |
Output is correct |
6 |
Correct |
11 ms |
10488 KB |
Output is correct |
7 |
Correct |
11 ms |
10564 KB |
Output is correct |
8 |
Correct |
12 ms |
10532 KB |
Output is correct |
9 |
Correct |
11 ms |
10620 KB |
Output is correct |
10 |
Correct |
11 ms |
10492 KB |
Output is correct |
11 |
Correct |
11 ms |
10488 KB |
Output is correct |
12 |
Correct |
11 ms |
10536 KB |
Output is correct |
13 |
Correct |
11 ms |
10536 KB |
Output is correct |
14 |
Correct |
11 ms |
10464 KB |
Output is correct |
15 |
Correct |
11 ms |
10488 KB |
Output is correct |
16 |
Correct |
11 ms |
10488 KB |
Output is correct |
17 |
Correct |
11 ms |
10488 KB |
Output is correct |
18 |
Correct |
12 ms |
10488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
10552 KB |
Output is correct |
2 |
Correct |
12 ms |
10532 KB |
Output is correct |
3 |
Correct |
11 ms |
10488 KB |
Output is correct |
4 |
Correct |
11 ms |
10488 KB |
Output is correct |
5 |
Correct |
11 ms |
10488 KB |
Output is correct |
6 |
Correct |
11 ms |
10488 KB |
Output is correct |
7 |
Correct |
11 ms |
10564 KB |
Output is correct |
8 |
Correct |
12 ms |
10532 KB |
Output is correct |
9 |
Correct |
11 ms |
10620 KB |
Output is correct |
10 |
Correct |
11 ms |
10492 KB |
Output is correct |
11 |
Correct |
11 ms |
10488 KB |
Output is correct |
12 |
Correct |
11 ms |
10536 KB |
Output is correct |
13 |
Correct |
11 ms |
10536 KB |
Output is correct |
14 |
Correct |
11 ms |
10464 KB |
Output is correct |
15 |
Correct |
11 ms |
10488 KB |
Output is correct |
16 |
Correct |
11 ms |
10488 KB |
Output is correct |
17 |
Correct |
11 ms |
10488 KB |
Output is correct |
18 |
Correct |
12 ms |
10488 KB |
Output is correct |
19 |
Correct |
11 ms |
10488 KB |
Output is correct |
20 |
Correct |
11 ms |
10548 KB |
Output is correct |
21 |
Correct |
13 ms |
10660 KB |
Output is correct |
22 |
Correct |
15 ms |
14200 KB |
Output is correct |
23 |
Correct |
15 ms |
13532 KB |
Output is correct |
24 |
Correct |
15 ms |
13992 KB |
Output is correct |
25 |
Correct |
15 ms |
13944 KB |
Output is correct |
26 |
Correct |
13 ms |
11896 KB |
Output is correct |
27 |
Correct |
16 ms |
13820 KB |
Output is correct |
28 |
Correct |
13 ms |
11436 KB |
Output is correct |
29 |
Correct |
12 ms |
11896 KB |
Output is correct |
30 |
Correct |
14 ms |
12044 KB |
Output is correct |
31 |
Correct |
15 ms |
13176 KB |
Output is correct |
32 |
Correct |
15 ms |
13432 KB |
Output is correct |
33 |
Correct |
16 ms |
13816 KB |
Output is correct |
34 |
Correct |
14 ms |
13052 KB |
Output is correct |
35 |
Correct |
15 ms |
13816 KB |
Output is correct |
36 |
Correct |
15 ms |
14244 KB |
Output is correct |
37 |
Correct |
15 ms |
13688 KB |
Output is correct |
38 |
Correct |
14 ms |
12636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
10552 KB |
Output is correct |
2 |
Correct |
12 ms |
10532 KB |
Output is correct |
3 |
Correct |
11 ms |
10488 KB |
Output is correct |
4 |
Correct |
11 ms |
10488 KB |
Output is correct |
5 |
Correct |
11 ms |
10488 KB |
Output is correct |
6 |
Correct |
11 ms |
10488 KB |
Output is correct |
7 |
Correct |
11 ms |
10564 KB |
Output is correct |
8 |
Correct |
12 ms |
10532 KB |
Output is correct |
9 |
Correct |
11 ms |
10620 KB |
Output is correct |
10 |
Correct |
11 ms |
10492 KB |
Output is correct |
11 |
Correct |
11 ms |
10488 KB |
Output is correct |
12 |
Correct |
11 ms |
10536 KB |
Output is correct |
13 |
Correct |
11 ms |
10536 KB |
Output is correct |
14 |
Correct |
11 ms |
10464 KB |
Output is correct |
15 |
Correct |
11 ms |
10488 KB |
Output is correct |
16 |
Correct |
11 ms |
10488 KB |
Output is correct |
17 |
Correct |
11 ms |
10488 KB |
Output is correct |
18 |
Correct |
12 ms |
10488 KB |
Output is correct |
19 |
Correct |
256 ms |
19856 KB |
Output is correct |
20 |
Correct |
269 ms |
19848 KB |
Output is correct |
21 |
Correct |
270 ms |
19860 KB |
Output is correct |
22 |
Correct |
351 ms |
20000 KB |
Output is correct |
23 |
Correct |
189 ms |
19932 KB |
Output is correct |
24 |
Correct |
119 ms |
20236 KB |
Output is correct |
25 |
Correct |
262 ms |
21808 KB |
Output is correct |
26 |
Correct |
161 ms |
23652 KB |
Output is correct |
27 |
Correct |
344 ms |
30260 KB |
Output is correct |
28 |
Correct |
523 ms |
37092 KB |
Output is correct |
29 |
Correct |
557 ms |
36556 KB |
Output is correct |
30 |
Correct |
334 ms |
30328 KB |
Output is correct |
31 |
Correct |
344 ms |
30396 KB |
Output is correct |
32 |
Correct |
379 ms |
30276 KB |
Output is correct |
33 |
Correct |
466 ms |
29128 KB |
Output is correct |
34 |
Correct |
428 ms |
30072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
10552 KB |
Output is correct |
2 |
Correct |
12 ms |
10532 KB |
Output is correct |
3 |
Correct |
11 ms |
10488 KB |
Output is correct |
4 |
Correct |
11 ms |
10488 KB |
Output is correct |
5 |
Correct |
11 ms |
10488 KB |
Output is correct |
6 |
Correct |
11 ms |
10488 KB |
Output is correct |
7 |
Correct |
11 ms |
10564 KB |
Output is correct |
8 |
Correct |
12 ms |
10532 KB |
Output is correct |
9 |
Correct |
11 ms |
10620 KB |
Output is correct |
10 |
Correct |
11 ms |
10492 KB |
Output is correct |
11 |
Correct |
11 ms |
10488 KB |
Output is correct |
12 |
Correct |
11 ms |
10536 KB |
Output is correct |
13 |
Correct |
11 ms |
10536 KB |
Output is correct |
14 |
Correct |
11 ms |
10464 KB |
Output is correct |
15 |
Correct |
11 ms |
10488 KB |
Output is correct |
16 |
Correct |
11 ms |
10488 KB |
Output is correct |
17 |
Correct |
11 ms |
10488 KB |
Output is correct |
18 |
Correct |
12 ms |
10488 KB |
Output is correct |
19 |
Correct |
11 ms |
10488 KB |
Output is correct |
20 |
Correct |
11 ms |
10548 KB |
Output is correct |
21 |
Correct |
13 ms |
10660 KB |
Output is correct |
22 |
Correct |
15 ms |
14200 KB |
Output is correct |
23 |
Correct |
15 ms |
13532 KB |
Output is correct |
24 |
Correct |
15 ms |
13992 KB |
Output is correct |
25 |
Correct |
15 ms |
13944 KB |
Output is correct |
26 |
Correct |
13 ms |
11896 KB |
Output is correct |
27 |
Correct |
16 ms |
13820 KB |
Output is correct |
28 |
Correct |
13 ms |
11436 KB |
Output is correct |
29 |
Correct |
12 ms |
11896 KB |
Output is correct |
30 |
Correct |
14 ms |
12044 KB |
Output is correct |
31 |
Correct |
15 ms |
13176 KB |
Output is correct |
32 |
Correct |
15 ms |
13432 KB |
Output is correct |
33 |
Correct |
16 ms |
13816 KB |
Output is correct |
34 |
Correct |
14 ms |
13052 KB |
Output is correct |
35 |
Correct |
15 ms |
13816 KB |
Output is correct |
36 |
Correct |
15 ms |
14244 KB |
Output is correct |
37 |
Correct |
15 ms |
13688 KB |
Output is correct |
38 |
Correct |
14 ms |
12636 KB |
Output is correct |
39 |
Correct |
256 ms |
19856 KB |
Output is correct |
40 |
Correct |
269 ms |
19848 KB |
Output is correct |
41 |
Correct |
270 ms |
19860 KB |
Output is correct |
42 |
Correct |
351 ms |
20000 KB |
Output is correct |
43 |
Correct |
189 ms |
19932 KB |
Output is correct |
44 |
Correct |
119 ms |
20236 KB |
Output is correct |
45 |
Correct |
262 ms |
21808 KB |
Output is correct |
46 |
Correct |
161 ms |
23652 KB |
Output is correct |
47 |
Correct |
344 ms |
30260 KB |
Output is correct |
48 |
Correct |
523 ms |
37092 KB |
Output is correct |
49 |
Correct |
557 ms |
36556 KB |
Output is correct |
50 |
Correct |
334 ms |
30328 KB |
Output is correct |
51 |
Correct |
344 ms |
30396 KB |
Output is correct |
52 |
Correct |
379 ms |
30276 KB |
Output is correct |
53 |
Correct |
466 ms |
29128 KB |
Output is correct |
54 |
Correct |
428 ms |
30072 KB |
Output is correct |
55 |
Correct |
27 ms |
11512 KB |
Output is correct |
56 |
Correct |
27 ms |
11384 KB |
Output is correct |
57 |
Correct |
123 ms |
19768 KB |
Output is correct |
58 |
Correct |
59 ms |
20328 KB |
Output is correct |
59 |
Correct |
149 ms |
24312 KB |
Output is correct |
60 |
Correct |
1054 ms |
40464 KB |
Output is correct |
61 |
Correct |
364 ms |
30584 KB |
Output is correct |
62 |
Correct |
407 ms |
34288 KB |
Output is correct |
63 |
Correct |
572 ms |
34296 KB |
Output is correct |
64 |
Correct |
975 ms |
31972 KB |
Output is correct |
65 |
Correct |
393 ms |
30456 KB |
Output is correct |
66 |
Correct |
774 ms |
39416 KB |
Output is correct |
67 |
Correct |
227 ms |
35168 KB |
Output is correct |
68 |
Correct |
510 ms |
35072 KB |
Output is correct |
69 |
Correct |
506 ms |
35324 KB |
Output is correct |
70 |
Correct |
469 ms |
34040 KB |
Output is correct |