#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define itr ::iterator
const int MAX=3e5;
const ll INF=1e9;
typedef pair<ll,ll> pii;
map<ll,ll> maps;
vector<pii> later,vec[MAX];
ll K,res,height[MAX],SubSize[MAX],Special[MAX],Weight[MAX];
void Prepare(int node,int par,int hei)
{
SubSize[node]=1;
height[node]=hei;
for(auto A:vec[node])
{
if(A.first==par)
continue;
Weight[A.first]=Weight[node]+A.second;
Prepare(A.first,node,hei+1);
SubSize[node]+=SubSize[A.first];
}
pii cur=mp(-1,-1);
for(auto A:vec[node])
{
if(A.first==par)
continue;
cur=max(cur,mp(SubSize[A.first],A.first));
}
Special[node]=cur.second;
return ;
}
void relax(ll x,ll y)
{
if(maps.count(x))
maps[x]=min(maps[x],y);
else
maps[x]=y;
}
void cal(int node,int par,int CurrentRoot)
{
later.pb(mp(Weight[node],height[node]));
if(maps.count(K+2*Weight[CurrentRoot]-Weight[node]))
{
//cout<<CurrentRoot<<" "<<node<<" "<<Weight[CurrentRoot]<<" "<<Weight[node]<<" required more "<<K+2*Weight[CurrentRoot]-Weight[node]<<"\n";
res=min(res,height[node]-height[CurrentRoot]+maps[K+2*Weight[CurrentRoot]-Weight[node]]-height[CurrentRoot]);
}
if(Weight[node]-Weight[CurrentRoot]==K)
res=min(res,height[node]-height[CurrentRoot]);
for(auto A:vec[node])
{
if(A.first==par)
continue;
cal(A.first,node,CurrentRoot);
}
return ;
}
void dfs(int node,int par)
{
for(auto A:vec[node])
{
if(A.first==par or Special[node]==A.first)
continue;
dfs(A.first,node);
}
if(Special[node]>=0)
{
dfs(Special[node],node);
if(maps.count(Weight[node]+K))
{
// cout<<node<<" "<<Weight[node]<<"\n";
res=min(res,maps[Weight[node]+K]-height[node]);
}
}
//cout<<"cuurent node "<<node<<"\n";
//for(auto A:maps)
// cout<<A.first<<" "<<A.second<<"\n";
for(auto A:vec[node])
{
if(A.first==par or A.first==Special[node])
continue;
cal(A.first,node,node);
for(auto A:later)
relax(A.first,A.second);
later.clear();
}
if(par<0)
maps.clear();
else if(Special[par]!=node)
maps.clear();
else
relax(Weight[node],height[node]);
return ;
}
int best_path(int N,int K_,int H[][2],int L[])
{
K=K_;
for(int A=0;A<N-1;A++)
{
vec[H[A][0]].pb(mp(H[A][1],L[A]));
vec[H[A][1]].pb(mp(H[A][0],L[A]));
}
res=INF;
Prepare(0,-1,0);
dfs(0,-1);
if(res==INF)
res=-1;
return res;
}
/*int main()
{
ios_base::sync_with_stdio(false);
int N=11,K=12;
int L[]={3,
4,
5,
4,
6,
3,
2,
5,
6,
7};
int H[][2]={{0,1},
{0,2},
{2,3},
{3,4},
{4,5},
{0,6},
{6,7},
{6,8},
{8,9},
{8,10}};
//N=4,K=3;
//int H[][2]={{0,1},{1,2},{1,3}},L[]={1,2,4};
cout<<best_path(N,K,H,L);
return 0;
}*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
8 ms |
7524 KB |
Output is correct |
3 |
Correct |
8 ms |
7600 KB |
Output is correct |
4 |
Correct |
9 ms |
7680 KB |
Output is correct |
5 |
Correct |
8 ms |
7680 KB |
Output is correct |
6 |
Correct |
8 ms |
7688 KB |
Output is correct |
7 |
Correct |
8 ms |
7688 KB |
Output is correct |
8 |
Correct |
7 ms |
7688 KB |
Output is correct |
9 |
Correct |
8 ms |
7688 KB |
Output is correct |
10 |
Correct |
10 ms |
7688 KB |
Output is correct |
11 |
Correct |
8 ms |
7688 KB |
Output is correct |
12 |
Correct |
8 ms |
7688 KB |
Output is correct |
13 |
Correct |
8 ms |
7688 KB |
Output is correct |
14 |
Correct |
8 ms |
7780 KB |
Output is correct |
15 |
Correct |
7 ms |
7780 KB |
Output is correct |
16 |
Correct |
8 ms |
7780 KB |
Output is correct |
17 |
Correct |
8 ms |
7780 KB |
Output is correct |
18 |
Correct |
9 ms |
7780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
8 ms |
7524 KB |
Output is correct |
3 |
Correct |
8 ms |
7600 KB |
Output is correct |
4 |
Correct |
9 ms |
7680 KB |
Output is correct |
5 |
Correct |
8 ms |
7680 KB |
Output is correct |
6 |
Correct |
8 ms |
7688 KB |
Output is correct |
7 |
Correct |
8 ms |
7688 KB |
Output is correct |
8 |
Correct |
7 ms |
7688 KB |
Output is correct |
9 |
Correct |
8 ms |
7688 KB |
Output is correct |
10 |
Correct |
10 ms |
7688 KB |
Output is correct |
11 |
Correct |
8 ms |
7688 KB |
Output is correct |
12 |
Correct |
8 ms |
7688 KB |
Output is correct |
13 |
Correct |
8 ms |
7688 KB |
Output is correct |
14 |
Correct |
8 ms |
7780 KB |
Output is correct |
15 |
Correct |
7 ms |
7780 KB |
Output is correct |
16 |
Correct |
8 ms |
7780 KB |
Output is correct |
17 |
Correct |
8 ms |
7780 KB |
Output is correct |
18 |
Correct |
9 ms |
7780 KB |
Output is correct |
19 |
Correct |
7 ms |
7780 KB |
Output is correct |
20 |
Correct |
9 ms |
7780 KB |
Output is correct |
21 |
Correct |
10 ms |
7780 KB |
Output is correct |
22 |
Correct |
9 ms |
7804 KB |
Output is correct |
23 |
Correct |
11 ms |
7932 KB |
Output is correct |
24 |
Correct |
10 ms |
7932 KB |
Output is correct |
25 |
Correct |
9 ms |
7932 KB |
Output is correct |
26 |
Correct |
10 ms |
7932 KB |
Output is correct |
27 |
Correct |
8 ms |
7932 KB |
Output is correct |
28 |
Correct |
9 ms |
7932 KB |
Output is correct |
29 |
Correct |
9 ms |
7932 KB |
Output is correct |
30 |
Correct |
9 ms |
7932 KB |
Output is correct |
31 |
Correct |
9 ms |
7932 KB |
Output is correct |
32 |
Correct |
10 ms |
7932 KB |
Output is correct |
33 |
Correct |
9 ms |
7932 KB |
Output is correct |
34 |
Correct |
9 ms |
7932 KB |
Output is correct |
35 |
Correct |
9 ms |
7932 KB |
Output is correct |
36 |
Correct |
9 ms |
7932 KB |
Output is correct |
37 |
Correct |
8 ms |
7932 KB |
Output is correct |
38 |
Correct |
9 ms |
7932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
8 ms |
7524 KB |
Output is correct |
3 |
Correct |
8 ms |
7600 KB |
Output is correct |
4 |
Correct |
9 ms |
7680 KB |
Output is correct |
5 |
Correct |
8 ms |
7680 KB |
Output is correct |
6 |
Correct |
8 ms |
7688 KB |
Output is correct |
7 |
Correct |
8 ms |
7688 KB |
Output is correct |
8 |
Correct |
7 ms |
7688 KB |
Output is correct |
9 |
Correct |
8 ms |
7688 KB |
Output is correct |
10 |
Correct |
10 ms |
7688 KB |
Output is correct |
11 |
Correct |
8 ms |
7688 KB |
Output is correct |
12 |
Correct |
8 ms |
7688 KB |
Output is correct |
13 |
Correct |
8 ms |
7688 KB |
Output is correct |
14 |
Correct |
8 ms |
7780 KB |
Output is correct |
15 |
Correct |
7 ms |
7780 KB |
Output is correct |
16 |
Correct |
8 ms |
7780 KB |
Output is correct |
17 |
Correct |
8 ms |
7780 KB |
Output is correct |
18 |
Correct |
9 ms |
7780 KB |
Output is correct |
19 |
Correct |
304 ms |
18304 KB |
Output is correct |
20 |
Correct |
216 ms |
18304 KB |
Output is correct |
21 |
Correct |
299 ms |
18304 KB |
Output is correct |
22 |
Correct |
256 ms |
18304 KB |
Output is correct |
23 |
Correct |
357 ms |
18304 KB |
Output is correct |
24 |
Correct |
213 ms |
18304 KB |
Output is correct |
25 |
Correct |
153 ms |
23924 KB |
Output is correct |
26 |
Correct |
85 ms |
28964 KB |
Output is correct |
27 |
Correct |
315 ms |
31596 KB |
Output is correct |
28 |
Correct |
416 ms |
67608 KB |
Output is correct |
29 |
Correct |
480 ms |
69208 KB |
Output is correct |
30 |
Correct |
290 ms |
69208 KB |
Output is correct |
31 |
Correct |
292 ms |
69208 KB |
Output is correct |
32 |
Correct |
433 ms |
69208 KB |
Output is correct |
33 |
Correct |
566 ms |
69208 KB |
Output is correct |
34 |
Correct |
762 ms |
69208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7416 KB |
Output is correct |
2 |
Correct |
8 ms |
7524 KB |
Output is correct |
3 |
Correct |
8 ms |
7600 KB |
Output is correct |
4 |
Correct |
9 ms |
7680 KB |
Output is correct |
5 |
Correct |
8 ms |
7680 KB |
Output is correct |
6 |
Correct |
8 ms |
7688 KB |
Output is correct |
7 |
Correct |
8 ms |
7688 KB |
Output is correct |
8 |
Correct |
7 ms |
7688 KB |
Output is correct |
9 |
Correct |
8 ms |
7688 KB |
Output is correct |
10 |
Correct |
10 ms |
7688 KB |
Output is correct |
11 |
Correct |
8 ms |
7688 KB |
Output is correct |
12 |
Correct |
8 ms |
7688 KB |
Output is correct |
13 |
Correct |
8 ms |
7688 KB |
Output is correct |
14 |
Correct |
8 ms |
7780 KB |
Output is correct |
15 |
Correct |
7 ms |
7780 KB |
Output is correct |
16 |
Correct |
8 ms |
7780 KB |
Output is correct |
17 |
Correct |
8 ms |
7780 KB |
Output is correct |
18 |
Correct |
9 ms |
7780 KB |
Output is correct |
19 |
Correct |
7 ms |
7780 KB |
Output is correct |
20 |
Correct |
9 ms |
7780 KB |
Output is correct |
21 |
Correct |
10 ms |
7780 KB |
Output is correct |
22 |
Correct |
9 ms |
7804 KB |
Output is correct |
23 |
Correct |
11 ms |
7932 KB |
Output is correct |
24 |
Correct |
10 ms |
7932 KB |
Output is correct |
25 |
Correct |
9 ms |
7932 KB |
Output is correct |
26 |
Correct |
10 ms |
7932 KB |
Output is correct |
27 |
Correct |
8 ms |
7932 KB |
Output is correct |
28 |
Correct |
9 ms |
7932 KB |
Output is correct |
29 |
Correct |
9 ms |
7932 KB |
Output is correct |
30 |
Correct |
9 ms |
7932 KB |
Output is correct |
31 |
Correct |
9 ms |
7932 KB |
Output is correct |
32 |
Correct |
10 ms |
7932 KB |
Output is correct |
33 |
Correct |
9 ms |
7932 KB |
Output is correct |
34 |
Correct |
9 ms |
7932 KB |
Output is correct |
35 |
Correct |
9 ms |
7932 KB |
Output is correct |
36 |
Correct |
9 ms |
7932 KB |
Output is correct |
37 |
Correct |
8 ms |
7932 KB |
Output is correct |
38 |
Correct |
9 ms |
7932 KB |
Output is correct |
39 |
Correct |
304 ms |
18304 KB |
Output is correct |
40 |
Correct |
216 ms |
18304 KB |
Output is correct |
41 |
Correct |
299 ms |
18304 KB |
Output is correct |
42 |
Correct |
256 ms |
18304 KB |
Output is correct |
43 |
Correct |
357 ms |
18304 KB |
Output is correct |
44 |
Correct |
213 ms |
18304 KB |
Output is correct |
45 |
Correct |
153 ms |
23924 KB |
Output is correct |
46 |
Correct |
85 ms |
28964 KB |
Output is correct |
47 |
Correct |
315 ms |
31596 KB |
Output is correct |
48 |
Correct |
416 ms |
67608 KB |
Output is correct |
49 |
Correct |
480 ms |
69208 KB |
Output is correct |
50 |
Correct |
290 ms |
69208 KB |
Output is correct |
51 |
Correct |
292 ms |
69208 KB |
Output is correct |
52 |
Correct |
433 ms |
69208 KB |
Output is correct |
53 |
Correct |
566 ms |
69208 KB |
Output is correct |
54 |
Correct |
762 ms |
69208 KB |
Output is correct |
55 |
Correct |
32 ms |
69208 KB |
Output is correct |
56 |
Correct |
23 ms |
69208 KB |
Output is correct |
57 |
Correct |
135 ms |
69208 KB |
Output is correct |
58 |
Correct |
71 ms |
69208 KB |
Output is correct |
59 |
Correct |
137 ms |
69208 KB |
Output is correct |
60 |
Correct |
401 ms |
92268 KB |
Output is correct |
61 |
Correct |
354 ms |
92268 KB |
Output is correct |
62 |
Correct |
275 ms |
92268 KB |
Output is correct |
63 |
Correct |
394 ms |
92268 KB |
Output is correct |
64 |
Correct |
790 ms |
92268 KB |
Output is correct |
65 |
Correct |
906 ms |
92268 KB |
Output is correct |
66 |
Correct |
463 ms |
108444 KB |
Output is correct |
67 |
Correct |
266 ms |
108444 KB |
Output is correct |
68 |
Correct |
595 ms |
108444 KB |
Output is correct |
69 |
Correct |
686 ms |
108444 KB |
Output is correct |
70 |
Correct |
570 ms |
108444 KB |
Output is correct |