#include <bits/stdc++.h>
#define ll long long int
using namespace std;
#pragma GCC optimize("Ofast")
void YES()
{
cout<<"YES\n";
}
void NO()
{
cout<<"NO\n";
}
ll n;
int answer = 2e9;
vector<ll> cnt;
vector<ll> par;
vector<ll> dist;
vector<ll> eddist;
vector<vector<ll>> st;
vector<ll> tin;
vector<ll> ins;
vector<ll> first;
vector<ll> inv;
vector<ll> po(200001,-1);
unordered_map<ll,ll> oc[200000][2];
ll k;
ll T = 0;
void dfs2(ll v,vector<vector<vector<ll>>> & ed)
{
tin[v] = ++T;
inv[T] = v;
first[v] = ins.size();
ins.push_back(tin[v]);
for (vector<ll> i : ed[v])
{
ll u = i[0];
if (!tin[u])
{
eddist[u] = eddist[v]+1;
dist[u] = dist[v]+i[1];
dfs2(u,ed);
ins.push_back(tin[v]);
}
}
}
void dfs(ll v,ll pr,vector<vector<vector<ll>>> & ed)
{
cnt[v] = 1;
for (vector<ll> i : ed[v])
{
ll u = i[0];
if (par[u] != -1 || u == pr) continue;
dfs(u,v,ed);
cnt[v]+=cnt[u];
}
}
ll cent(ll v,ll pr,ll s,vector<vector<vector<ll>>> & ed)
{
for (vector<ll> i : ed[v])
{
ll u = i[0];
if (u != pr && par[u] == -1 && cnt[u] > s/2)
{
return cent(u,v,s,ed);
}
}
return v;
}
ll findlca(ll a,ll b)
{
a = first[a],b = first[b];
if (a > b) swap(a,b);
ll k = po[b-a+1];
return inv[min(st[k][a],st[k][b-(1 << k)+1])];
}
vector<ll> d;
ll lca;
vector<ll> finddist(ll u,ll v)
{
lca = findlca(u,v);
return {dist[u]+dist[v]-2*dist[lca],eddist[u]+eddist[v]-2*eddist[lca]};
}
void paint(ll v,ll u)
{
if (v == -2) return;
d = finddist(u,v);
if (d[0] <= k)
{
if (oc[v][1].find(d[0]) != oc[v][1].end()) oc[v][1][d[0]] = min(oc[v][1][d[0]],d[1]);
else oc[v][1][d[0]] = d[1];
}
paint(par[v],u);
}
ll decomp(ll v,ll pr,vector<vector<vector<ll>>> & ed)
{
dfs(v,-1,ed);
ll s = cnt[v];
ll c = cent(v,-1,s,ed);
par[c] = pr;
paint(c,c);
oc[c][0][0]=0;
// cout<<c+1<<" ";
// cout<<c<<" "<<pr<<" "<<par[c]<<"\n";
for (vector<ll> & i : ed[c])
{
ll u = i[0];
if (par[u] == -1)
{
decomp(u,c,ed);
// cout<<cen<<" ";
for (auto & i : oc[c][1])
{
if (oc[c][0].find(k-i.first) == oc[c][0].end()) continue;
answer = min(answer,int(i.second+oc[c][0][k-i.first]));
}
for (auto & i : oc[c][1])
{
if (oc[c][0].find(i.first) == oc[c][0].end()) oc[c][0][i.first] = i.second;
else oc[c][0][i.first] = min(oc[c][0][i.first],i.second);
}
oc[c][1].clear();
}
}
// cout<<c<<"\n";
// for (auto i : oc[c][0])
// {
// cout<<i.first<<" "<<i.second<<"\n";
// }
return c;
}
ll best_path(int n,int K,int H[][2],int L[])
{
ll p = 0,d = 1;
k = K;
if (po[1] == -1)
{
for (ll e = 1;e<=200000;e++)
{
if (e == d*2)
{
p++;
d*=2;
}
po[e] = p;
}
}
eddist = vector<ll>(n,0);
tin = vector<ll>(n,0);
cnt = vector<ll>(n,0);
par = vector<ll>(n,-1);
first = vector<ll>(n,0);
dist = vector<ll>(n,0);
inv = vector<ll>(n+1,0);
st = vector<vector<ll>>(2*n,vector<ll>(0));
vector<vector<vector<ll>>> ed(n);
for (ll e = 0;e<n;e++)
{
oc[e][0].clear();
oc[e][1].clear();
}
for (ll e = 0;e<n-1;e++)
{
ll u = H[e][0],v = H[e][1],we = L[e];
ed[u].push_back({v,we});
ed[v].push_back({u,we});
}
dfs2(0,ed);
answer = 2e9;
for (ll e = 0;e<(ll)ins.size();e++)
{
st[0].push_back(ins[e]);
}
for (ll k = 1;k<20;k++)
{
ll po = (1 << (k-1));
for (ll e = 0;e<(ll)ins.size()-po*2+1;e++)
{
st[k].push_back(min(st[k-1][e],st[k-1][e+po]));
}
}
// if (n > 1000) return 1;
decomp(0,-2,ed);
if (answer == 2e9) return -1;
return answer;
}
void ans()
{
ll n,k;cin>>n>>k;
int H[n-1][2],L[n-1];
for (ll e = 0;e<n-1;e++)
{
ll u,v;cin>>u>>v;
H[e][0] = u;H[e][1] = v;
}
for (ll e = 0;e<n-1;e++)
{
ll we;cin>>we;
L[e] = we;
}
cout<<best_path(n,k,H,L)<<"\n";
}
// int main()
// {
// cin.tie(0);cout.tie(0);
// ios_base::sync_with_stdio(0);
// ll t = 1;
// for (ll e = 1;e<=t;e++)
// {
// ans();
// }
// return 0;
// }
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
27484 KB |
Output is correct |
2 |
Correct |
8 ms |
27652 KB |
Output is correct |
3 |
Correct |
8 ms |
27484 KB |
Output is correct |
4 |
Correct |
8 ms |
27484 KB |
Output is correct |
5 |
Correct |
7 ms |
27484 KB |
Output is correct |
6 |
Correct |
7 ms |
27484 KB |
Output is correct |
7 |
Correct |
7 ms |
27484 KB |
Output is correct |
8 |
Correct |
7 ms |
27484 KB |
Output is correct |
9 |
Correct |
7 ms |
27484 KB |
Output is correct |
10 |
Correct |
7 ms |
27484 KB |
Output is correct |
11 |
Correct |
8 ms |
27484 KB |
Output is correct |
12 |
Correct |
8 ms |
27484 KB |
Output is correct |
13 |
Correct |
8 ms |
27656 KB |
Output is correct |
14 |
Correct |
8 ms |
27484 KB |
Output is correct |
15 |
Correct |
7 ms |
27484 KB |
Output is correct |
16 |
Correct |
7 ms |
27480 KB |
Output is correct |
17 |
Correct |
7 ms |
27484 KB |
Output is correct |
18 |
Correct |
7 ms |
27648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
27484 KB |
Output is correct |
2 |
Correct |
8 ms |
27652 KB |
Output is correct |
3 |
Correct |
8 ms |
27484 KB |
Output is correct |
4 |
Correct |
8 ms |
27484 KB |
Output is correct |
5 |
Correct |
7 ms |
27484 KB |
Output is correct |
6 |
Correct |
7 ms |
27484 KB |
Output is correct |
7 |
Correct |
7 ms |
27484 KB |
Output is correct |
8 |
Correct |
7 ms |
27484 KB |
Output is correct |
9 |
Correct |
7 ms |
27484 KB |
Output is correct |
10 |
Correct |
7 ms |
27484 KB |
Output is correct |
11 |
Correct |
8 ms |
27484 KB |
Output is correct |
12 |
Correct |
8 ms |
27484 KB |
Output is correct |
13 |
Correct |
8 ms |
27656 KB |
Output is correct |
14 |
Correct |
8 ms |
27484 KB |
Output is correct |
15 |
Correct |
7 ms |
27484 KB |
Output is correct |
16 |
Correct |
7 ms |
27480 KB |
Output is correct |
17 |
Correct |
7 ms |
27484 KB |
Output is correct |
18 |
Correct |
7 ms |
27648 KB |
Output is correct |
19 |
Correct |
7 ms |
27480 KB |
Output is correct |
20 |
Correct |
8 ms |
27480 KB |
Output is correct |
21 |
Correct |
9 ms |
28252 KB |
Output is correct |
22 |
Correct |
10 ms |
28116 KB |
Output is correct |
23 |
Correct |
10 ms |
28248 KB |
Output is correct |
24 |
Correct |
9 ms |
28252 KB |
Output is correct |
25 |
Correct |
11 ms |
28252 KB |
Output is correct |
26 |
Correct |
10 ms |
28252 KB |
Output is correct |
27 |
Correct |
9 ms |
28252 KB |
Output is correct |
28 |
Correct |
9 ms |
28252 KB |
Output is correct |
29 |
Correct |
10 ms |
28248 KB |
Output is correct |
30 |
Correct |
11 ms |
28252 KB |
Output is correct |
31 |
Correct |
10 ms |
28252 KB |
Output is correct |
32 |
Correct |
10 ms |
28248 KB |
Output is correct |
33 |
Correct |
13 ms |
28508 KB |
Output is correct |
34 |
Correct |
12 ms |
28248 KB |
Output is correct |
35 |
Correct |
9 ms |
28252 KB |
Output is correct |
36 |
Correct |
10 ms |
28252 KB |
Output is correct |
37 |
Correct |
10 ms |
28252 KB |
Output is correct |
38 |
Correct |
11 ms |
28508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
27484 KB |
Output is correct |
2 |
Correct |
8 ms |
27652 KB |
Output is correct |
3 |
Correct |
8 ms |
27484 KB |
Output is correct |
4 |
Correct |
8 ms |
27484 KB |
Output is correct |
5 |
Correct |
7 ms |
27484 KB |
Output is correct |
6 |
Correct |
7 ms |
27484 KB |
Output is correct |
7 |
Correct |
7 ms |
27484 KB |
Output is correct |
8 |
Correct |
7 ms |
27484 KB |
Output is correct |
9 |
Correct |
7 ms |
27484 KB |
Output is correct |
10 |
Correct |
7 ms |
27484 KB |
Output is correct |
11 |
Correct |
8 ms |
27484 KB |
Output is correct |
12 |
Correct |
8 ms |
27484 KB |
Output is correct |
13 |
Correct |
8 ms |
27656 KB |
Output is correct |
14 |
Correct |
8 ms |
27484 KB |
Output is correct |
15 |
Correct |
7 ms |
27484 KB |
Output is correct |
16 |
Correct |
7 ms |
27480 KB |
Output is correct |
17 |
Correct |
7 ms |
27484 KB |
Output is correct |
18 |
Correct |
7 ms |
27648 KB |
Output is correct |
19 |
Correct |
475 ms |
120376 KB |
Output is correct |
20 |
Correct |
474 ms |
121412 KB |
Output is correct |
21 |
Correct |
468 ms |
119540 KB |
Output is correct |
22 |
Correct |
475 ms |
119016 KB |
Output is correct |
23 |
Correct |
430 ms |
115176 KB |
Output is correct |
24 |
Correct |
324 ms |
114676 KB |
Output is correct |
25 |
Correct |
419 ms |
117388 KB |
Output is correct |
26 |
Correct |
363 ms |
120260 KB |
Output is correct |
27 |
Runtime error |
2752 ms |
262144 KB |
Execution killed with signal 9 |
28 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
27484 KB |
Output is correct |
2 |
Correct |
8 ms |
27652 KB |
Output is correct |
3 |
Correct |
8 ms |
27484 KB |
Output is correct |
4 |
Correct |
8 ms |
27484 KB |
Output is correct |
5 |
Correct |
7 ms |
27484 KB |
Output is correct |
6 |
Correct |
7 ms |
27484 KB |
Output is correct |
7 |
Correct |
7 ms |
27484 KB |
Output is correct |
8 |
Correct |
7 ms |
27484 KB |
Output is correct |
9 |
Correct |
7 ms |
27484 KB |
Output is correct |
10 |
Correct |
7 ms |
27484 KB |
Output is correct |
11 |
Correct |
8 ms |
27484 KB |
Output is correct |
12 |
Correct |
8 ms |
27484 KB |
Output is correct |
13 |
Correct |
8 ms |
27656 KB |
Output is correct |
14 |
Correct |
8 ms |
27484 KB |
Output is correct |
15 |
Correct |
7 ms |
27484 KB |
Output is correct |
16 |
Correct |
7 ms |
27480 KB |
Output is correct |
17 |
Correct |
7 ms |
27484 KB |
Output is correct |
18 |
Correct |
7 ms |
27648 KB |
Output is correct |
19 |
Correct |
7 ms |
27480 KB |
Output is correct |
20 |
Correct |
8 ms |
27480 KB |
Output is correct |
21 |
Correct |
9 ms |
28252 KB |
Output is correct |
22 |
Correct |
10 ms |
28116 KB |
Output is correct |
23 |
Correct |
10 ms |
28248 KB |
Output is correct |
24 |
Correct |
9 ms |
28252 KB |
Output is correct |
25 |
Correct |
11 ms |
28252 KB |
Output is correct |
26 |
Correct |
10 ms |
28252 KB |
Output is correct |
27 |
Correct |
9 ms |
28252 KB |
Output is correct |
28 |
Correct |
9 ms |
28252 KB |
Output is correct |
29 |
Correct |
10 ms |
28248 KB |
Output is correct |
30 |
Correct |
11 ms |
28252 KB |
Output is correct |
31 |
Correct |
10 ms |
28252 KB |
Output is correct |
32 |
Correct |
10 ms |
28248 KB |
Output is correct |
33 |
Correct |
13 ms |
28508 KB |
Output is correct |
34 |
Correct |
12 ms |
28248 KB |
Output is correct |
35 |
Correct |
9 ms |
28252 KB |
Output is correct |
36 |
Correct |
10 ms |
28252 KB |
Output is correct |
37 |
Correct |
10 ms |
28252 KB |
Output is correct |
38 |
Correct |
11 ms |
28508 KB |
Output is correct |
39 |
Correct |
475 ms |
120376 KB |
Output is correct |
40 |
Correct |
474 ms |
121412 KB |
Output is correct |
41 |
Correct |
468 ms |
119540 KB |
Output is correct |
42 |
Correct |
475 ms |
119016 KB |
Output is correct |
43 |
Correct |
430 ms |
115176 KB |
Output is correct |
44 |
Correct |
324 ms |
114676 KB |
Output is correct |
45 |
Correct |
419 ms |
117388 KB |
Output is correct |
46 |
Correct |
363 ms |
120260 KB |
Output is correct |
47 |
Runtime error |
2752 ms |
262144 KB |
Execution killed with signal 9 |
48 |
Halted |
0 ms |
0 KB |
- |