Submission #906328

#	Time	Username	Problem	Language	Result	Execution time	Memory
906328		Belphegor	오두막집 (GA7_cabana)	C++14	100 / 100	4361 ms	18560 KiB

cabana

#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-1)*(250);
	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;
      |                     ^

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37