#include "race.h"
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define xx first
#define yy second
using namespace std;
typedef pair<int,int> ii;
vector<vector<ii> > to;
int k;
int subsz;
int sz[200020];
bool block[200020];
map<int,int> bag;
map<int,int> subbag;
int ans=1e9;
void dosz(int u,int pre){
sz[u]=1;
for(ii vw : to[u]){
int v=vw.xx;
if((v!=pre)&&(!block[v])){
dosz(v,u);
sz[u]+=sz[v];
}
}
}
int findcentr(int u,int pre){
for(ii vw : to[u]){
int v=vw.xx;
if((v!=pre)&&(!block[v])){
if(sz[v]>subsz/2) return findcentr(v,u);
}
}
return u;
}
void putwt(int u,int pre,int w,int l){
if(subbag.find(w)!=subbag.end()){
subbag[w]=min(subbag[w],l);
}
else{
subbag[w]=l;
}
for(ii vw : to[u]){
int v=vw.xx,ww=vw.yy;
if((v!=pre)&&(!block[v])){
putwt(v,u,w+ww,l+1);
}
}
}
void solve(int x,int i){
dosz(x,x);
subsz=sz[x];
int centr=findcentr(x,x);
// int centr = x;
block[centr]=1;
bag.clear();
// if(i==1) cout << centr << "#####################\n";
// cout << i << '\n' << ans << '\n';
for(ii sub : to[centr]){
int v=sub.xx,ww=sub.yy;
if(!block[v]){
subbag.clear();
putwt(v,v,ww,1);
// if(i==1) cout << v << "\\\n";
//K jintei centroid hurtel
if(subbag.find(k)!=subbag.end()) ans=min(ans,subbag[k]);
//bag & subbag
for(auto item : subbag){
int subw=item.xx,subl=item.yy;
// if(i==1) cout << subw << ":" << subl << endl;
if(bag.find(k-subw)!=bag.end()){
ans=min(ans,subl+bag[k-subw]);
}
}
for(auto item : subbag){ //merge
int subw=item.xx,subl=item.yy;
if(bag.find(subw)!=bag.end()){
bag[subw]=min(bag[subw],subl);
}
else{
bag[subw]=subl;
}
}
}
}
// cout << '\n' << "######################\n";
for(ii vw : to[centr]){
int v=vw.xx;
if(!block[v]){
solve(v,i+1);
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
to.assign(N+1,vector<ii>());
k=K;
for(int i=0;i<N-1;i++){
int u=H[i][0],v=H[i][1],w=L[i];
to[u].pb(mp(v,w));
to[v].pb(mp(u,w));
}
solve(0,0);
// cout << ans << endl;
// cout << "#################################\n";
return ans == 1e9 ? -1 : ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
3 ms |
384 KB |
Output is correct |
22 |
Correct |
4 ms |
512 KB |
Output is correct |
23 |
Correct |
4 ms |
512 KB |
Output is correct |
24 |
Correct |
4 ms |
512 KB |
Output is correct |
25 |
Correct |
3 ms |
512 KB |
Output is correct |
26 |
Correct |
3 ms |
512 KB |
Output is correct |
27 |
Correct |
3 ms |
384 KB |
Output is correct |
28 |
Correct |
4 ms |
512 KB |
Output is correct |
29 |
Correct |
4 ms |
512 KB |
Output is correct |
30 |
Correct |
4 ms |
512 KB |
Output is correct |
31 |
Correct |
4 ms |
512 KB |
Output is correct |
32 |
Correct |
4 ms |
512 KB |
Output is correct |
33 |
Correct |
5 ms |
512 KB |
Output is correct |
34 |
Correct |
4 ms |
512 KB |
Output is correct |
35 |
Correct |
4 ms |
512 KB |
Output is correct |
36 |
Correct |
4 ms |
512 KB |
Output is correct |
37 |
Correct |
4 ms |
512 KB |
Output is correct |
38 |
Correct |
4 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
368 ms |
9388 KB |
Output is correct |
20 |
Correct |
331 ms |
9336 KB |
Output is correct |
21 |
Correct |
305 ms |
9464 KB |
Output is correct |
22 |
Correct |
281 ms |
9436 KB |
Output is correct |
23 |
Correct |
470 ms |
9812 KB |
Output is correct |
24 |
Correct |
200 ms |
9640 KB |
Output is correct |
25 |
Correct |
270 ms |
13304 KB |
Output is correct |
26 |
Correct |
106 ms |
15096 KB |
Output is correct |
27 |
Correct |
431 ms |
18304 KB |
Output is correct |
28 |
Correct |
1623 ms |
43320 KB |
Output is correct |
29 |
Correct |
1772 ms |
42276 KB |
Output is correct |
30 |
Correct |
444 ms |
18168 KB |
Output is correct |
31 |
Correct |
432 ms |
18424 KB |
Output is correct |
32 |
Correct |
526 ms |
18160 KB |
Output is correct |
33 |
Correct |
837 ms |
17144 KB |
Output is correct |
34 |
Correct |
1668 ms |
28616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
3 ms |
384 KB |
Output is correct |
22 |
Correct |
4 ms |
512 KB |
Output is correct |
23 |
Correct |
4 ms |
512 KB |
Output is correct |
24 |
Correct |
4 ms |
512 KB |
Output is correct |
25 |
Correct |
3 ms |
512 KB |
Output is correct |
26 |
Correct |
3 ms |
512 KB |
Output is correct |
27 |
Correct |
3 ms |
384 KB |
Output is correct |
28 |
Correct |
4 ms |
512 KB |
Output is correct |
29 |
Correct |
4 ms |
512 KB |
Output is correct |
30 |
Correct |
4 ms |
512 KB |
Output is correct |
31 |
Correct |
4 ms |
512 KB |
Output is correct |
32 |
Correct |
4 ms |
512 KB |
Output is correct |
33 |
Correct |
5 ms |
512 KB |
Output is correct |
34 |
Correct |
4 ms |
512 KB |
Output is correct |
35 |
Correct |
4 ms |
512 KB |
Output is correct |
36 |
Correct |
4 ms |
512 KB |
Output is correct |
37 |
Correct |
4 ms |
512 KB |
Output is correct |
38 |
Correct |
4 ms |
512 KB |
Output is correct |
39 |
Correct |
368 ms |
9388 KB |
Output is correct |
40 |
Correct |
331 ms |
9336 KB |
Output is correct |
41 |
Correct |
305 ms |
9464 KB |
Output is correct |
42 |
Correct |
281 ms |
9436 KB |
Output is correct |
43 |
Correct |
470 ms |
9812 KB |
Output is correct |
44 |
Correct |
200 ms |
9640 KB |
Output is correct |
45 |
Correct |
270 ms |
13304 KB |
Output is correct |
46 |
Correct |
106 ms |
15096 KB |
Output is correct |
47 |
Correct |
431 ms |
18304 KB |
Output is correct |
48 |
Correct |
1623 ms |
43320 KB |
Output is correct |
49 |
Correct |
1772 ms |
42276 KB |
Output is correct |
50 |
Correct |
444 ms |
18168 KB |
Output is correct |
51 |
Correct |
432 ms |
18424 KB |
Output is correct |
52 |
Correct |
526 ms |
18160 KB |
Output is correct |
53 |
Correct |
837 ms |
17144 KB |
Output is correct |
54 |
Correct |
1668 ms |
28616 KB |
Output is correct |
55 |
Correct |
32 ms |
1664 KB |
Output is correct |
56 |
Correct |
18 ms |
1152 KB |
Output is correct |
57 |
Correct |
147 ms |
9732 KB |
Output is correct |
58 |
Correct |
52 ms |
9308 KB |
Output is correct |
59 |
Correct |
494 ms |
21008 KB |
Output is correct |
60 |
Correct |
1668 ms |
41904 KB |
Output is correct |
61 |
Correct |
483 ms |
19580 KB |
Output is correct |
62 |
Correct |
424 ms |
18264 KB |
Output is correct |
63 |
Correct |
504 ms |
18296 KB |
Output is correct |
64 |
Correct |
1529 ms |
24568 KB |
Output is correct |
65 |
Correct |
1342 ms |
27708 KB |
Output is correct |
66 |
Correct |
1676 ms |
40324 KB |
Output is correct |
67 |
Correct |
214 ms |
18460 KB |
Output is correct |
68 |
Correct |
802 ms |
26300 KB |
Output is correct |
69 |
Correct |
783 ms |
26360 KB |
Output is correct |
70 |
Correct |
718 ms |
25112 KB |
Output is correct |