oj.uz

Submission #906326

# Submission time Handle Problem Language Result Execution time Memory
906326 2024-01-14T02:43:43 Z Belphegor 오두막집 (GA7_cabana) C++14
30 / 100
 5384 ms 18736 KB 
#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);
		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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Correct 2 ms 4340 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 3 ms 4188 KB Output is correct
8 Correct 3 ms 4188 KB Output is correct
9 Correct 3 ms 4188 KB Output is correct
10 Correct 3 ms 4188 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4444 KB Output is correct
2 Correct 84 ms 4968 KB Output is correct
3 Correct 97 ms 5320 KB Output is correct
4 Correct 367 ms 7000 KB Output is correct
5 Correct 1195 ms 10076 KB Output is correct
6 Correct 3083 ms 13780 KB Output is correct
7 Correct 2646 ms 14520 KB Output is correct
8 Correct 4634 ms 16792 KB Output is correct
9 Correct 2966 ms 17080 KB Output is correct
10 Correct 4392 ms 18280 KB Output is correct
11 Correct 5010 ms 18616 KB Output is correct
12 Correct 5044 ms 18664 KB Output is correct
13 Correct 5366 ms 18736 KB Output is correct
14 Correct 5384 ms 18736 KB Output is correct
15 Correct 5325 ms 18736 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4184 KB Output is correct
2 Correct 2 ms 4188 KB Output is correct
3 Runtime error 5 ms 8540 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 8540 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 8572 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -