oj.uz

Submission #906327

# Submission time Handle Problem Language Result Execution time Memory
906327 2024-01-14T02:46:25 Z Belphegor 오두막집 (GA7_cabana) C++14
63 / 100
 6000 ms 17228 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);
		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

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 4188 KB Output is correct
4 Correct 3 ms 4188 KB Output is correct
5 Correct 2 ms 4188 KB Output is correct
6 Correct 3 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 4 ms 4700 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4440 KB Output is correct
2 Correct 80 ms 4952 KB Output is correct
3 Correct 101 ms 5328 KB Output is correct
4 Correct 370 ms 6748 KB Output is correct
5 Correct 1217 ms 10256 KB Output is correct
6 Correct 3261 ms 13768 KB Output is correct
7 Correct 2711 ms 14516 KB Output is correct
8 Correct 5002 ms 16788 KB Output is correct
9 Correct 3080 ms 15996 KB Output is correct
10 Correct 4591 ms 16932 KB Output is correct
11 Correct 5362 ms 17152 KB Output is correct
12 Correct 5449 ms 17180 KB Output is correct
13 Correct 5647 ms 17220 KB Output is correct
14 Correct 5640 ms 17228 KB Output is correct
15 Correct 5640 ms 17228 KB Output is correct

Subtask #3
12.0 / 12.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 4188 KB Output is correct
4 Correct 3 ms 4188 KB Output is correct
5 Correct 2 ms 4184 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 3 ms 4184 KB Output is correct
8 Correct 2 ms 4188 KB Output is correct
9 Correct 3 ms 4184 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4468 KB Output is correct
2 Correct 66 ms 4444 KB Output is correct
3 Correct 332 ms 5284 KB Output is correct
4 Correct 2137 ms 8328 KB Output is correct
5 Correct 883 ms 6400 KB Output is correct
6 Correct 1554 ms 7356 KB Output is correct
7 Correct 1945 ms 7944 KB Output is correct
8 Correct 3366 ms 8736 KB Output is correct
9 Correct 2166 ms 8272 KB Output is correct
10 Correct 3272 ms 8656 KB Output is correct
11 Correct 93 ms 4696 KB Output is correct
12 Correct 2273 ms 8320 KB Output is correct
13 Correct 5521 ms 9944 KB Output is correct
14 Correct 2278 ms 9236 KB Output is correct
15 Correct 5096 ms 10956 KB Output is correct
16 Correct 2836 ms 9200 KB Output is correct
17 Correct 2877 ms 9196 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4440 KB Output is correct
2 Correct 103 ms 4440 KB Output is correct
3 Correct 99 ms 4952 KB Output is correct
4 Correct 374 ms 5332 KB Output is correct
5 Correct 1646 ms 6576 KB Output is correct
6 Correct 3534 ms 8244 KB Output is correct
7 Correct 3675 ms 8264 KB Output is correct
8 Correct 4890 ms 9648 KB Output is correct
9 Correct 3212 ms 8768 KB Output is correct
10 Execution timed out 6039 ms 9672 KB Time limit exceeded
11 Halted 0 ms 0 KB -