This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int sz = 111111;
vector<pi>tree[sz+5];
bool v[sz+5],cabin[sz+5];
int sub[sz+5];
ll dist[sz+5],D,paths;
vector<ll>vals,tmp;
void DFS(int cur,int par){
if(cabin[cur] && par) vals.emplace_back(dist[cur]);
for(pi p : tree[cur]){
int nxt = p.first,w = p.second;
if(nxt == par || v[nxt]) continue;
dist[nxt] = dist[cur] + w;
DFS(nxt,cur);
}
}
ll DFS2(int cur,int par){
ll ret = 0;
if(cabin[cur]){
ret+=(int)(upper_bound(vals.begin(),vals.end(),D-dist[cur])-vals.begin());
tmp.emplace_back(dist[cur]);
}
for(pi p : tree[cur]){
int nxt = p.first,w = p.second;
if(v[nxt] || nxt == par) continue;
ret+=DFS2(nxt,cur);
}
return ret;
}
void dfs(int cur,int par){
sub[cur] = 1;
for(pi p : tree[cur]){
int nxt = p.first,w = p.second;
if(v[nxt] || nxt == par) continue;
dfs(nxt,cur);
sub[cur] += sub[nxt];
}
}
void decomposition(int cent){
dfs(cent,0);
int tot = sub[cent];
while(1){
int child = -1;
for(pi p : tree[cent]){
int nxt = p.first;
if(v[nxt] || sub[nxt] > sub[cent]) continue;
if(child == -1 || sub[child] < sub[nxt])
child = nxt;
}
if(child != -1 && sub[child]*2 > tot) cent = child;
else break;
}
vals.clear(); dist[cent] = 0;
DFS(cent,0);
sort(vals.begin(),vals.end());
ll cnt = 0;
if(cabin[cent]){
paths+=(int)(upper_bound(vals.begin(),vals.end(),D)-vals.begin());
}
for(pi p : tree[cent]){
int nxt = p.first,w = p.second;
if(v[nxt]) continue;
tmp.clear();
cnt+=DFS2(nxt,cent);
sort(tmp.begin(),tmp.end());
for(ll d : tmp){
cnt-=(int)(upper_bound(tmp.begin(),tmp.end(),D-d)-tmp.begin());
}
}
assert(cnt%2 == 0);
paths += cnt>>1;
v[cent] = 1;
for(pi p : tree[cent]){
int nxt = p.first;
if(v[nxt]) continue;
decomposition(nxt);
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
ll n,m,k; cin>>n>>m>>k;
for(int i=2; i<=n; i++){
ll p,d; cin>>p>>d;
assert(d<=1e9+7);
tree[p].emplace_back(pi(i,d));
tree[i].emplace_back(pi(p,d));
}
for(int i=1; i<=m; i++){
int x; cin>>x;
cabin[x] = 1;
}
ll l = 1,r = n*(1e9);
while(l<=r){
m = (l+r)>>1;
for(int i=1; i<=n; i++) v[i] = 0;
D = m; paths = 0;
decomposition(1);
if(paths < k) l = m+1;
else r = m-1;
}
cout<<l;
}
Compilation message (stderr)
cabana.cpp: In function 'll DFS2(int, int)':
cabana.cpp:27:21: warning: unused variable 'w' [-Wunused-variable]
27 | int nxt = p.first,w = p.second;
| ^
cabana.cpp: In function 'void dfs(int, int)':
cabana.cpp:36:21: warning: unused variable 'w' [-Wunused-variable]
36 | int nxt = p.first,w = p.second;
| ^
cabana.cpp: In function 'void decomposition(int)':
cabana.cpp:64:21: warning: unused variable 'w' [-Wunused-variable]
64 | int nxt = p.first,w = p.second;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |