oj.uz

Submission #906328

# Submission time Handle Problem Language Result Execution time Memory
906328 2024-01-14T02:50:00 Z Belphegor 오두막집 (GA7_cabana) C++14
100 / 100
 4361 ms 18560 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-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

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 4440 KB Output is correct
2 Correct 3 ms 4188 KB Output is correct
3 Correct 2 ms 4188 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 2 ms 4188 KB Output is correct
8 Correct 2 ms 4420 KB Output is correct
9 Correct 2 ms 4184 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4444 KB Output is correct
2 Correct 41 ms 4956 KB Output is correct
3 Correct 50 ms 5208 KB Output is correct
4 Correct 197 ms 6756 KB Output is correct
5 Correct 632 ms 10076 KB Output is correct
6 Correct 1738 ms 13672 KB Output is correct
7 Correct 1497 ms 14524 KB Output is correct
8 Correct 2812 ms 16784 KB Output is correct
9 Correct 1754 ms 15996 KB Output is correct
10 Correct 2622 ms 16928 KB Output is correct
11 Correct 2979 ms 17148 KB Output is correct
12 Correct 3119 ms 17188 KB Output is correct
13 Correct 2957 ms 17220 KB Output is correct
14 Correct 3077 ms 17228 KB Output is correct
15 Correct 3006 ms 17224 KB Output is correct

Subtask #3
12.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 Correct 2 ms 4188 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 2 ms 4188 KB Output is correct
8 Correct 2 ms 4188 KB Output is correct
9 Correct 2 ms 4188 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 7 ms 4444 KB Output is correct
2 Correct 38 ms 4640 KB Output is correct
3 Correct 171 ms 5208 KB Output is correct
4 Correct 1151 ms 8312 KB Output is correct
5 Correct 485 ms 6408 KB Output is correct
6 Correct 825 ms 7356 KB Output is correct
7 Correct 1025 ms 7952 KB Output is correct
8 Correct 1898 ms 8736 KB Output is correct
9 Correct 1243 ms 8312 KB Output is correct
10 Correct 1661 ms 8908 KB Output is correct
11 Correct 48 ms 4696 KB Output is correct
12 Correct 1219 ms 8320 KB Output is correct
13 Correct 3082 ms 9944 KB Output is correct
14 Correct 1308 ms 8524 KB Output is correct
15 Correct 2908 ms 9572 KB Output is correct
16 Correct 1578 ms 8276 KB Output is correct
17 Correct 1502 ms 8268 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4440 KB Output is correct
2 Correct 51 ms 5152 KB Output is correct
3 Correct 53 ms 4700 KB Output is correct
4 Correct 205 ms 5212 KB Output is correct
5 Correct 897 ms 6564 KB Output is correct
6 Correct 1955 ms 8252 KB Output is correct
7 Correct 1929 ms 8148 KB Output is correct
8 Correct 2861 ms 9652 KB Output is correct
9 Correct 1838 ms 8768 KB Output is correct
10 Correct 3215 ms 9680 KB Output is correct
11 Correct 2940 ms 11364 KB Output is correct
12 Correct 4003 ms 11496 KB Output is correct
13 Correct 3270 ms 10956 KB Output is correct
14 Correct 4361 ms 11576 KB Output is correct
15 Correct 3056 ms 11492 KB Output is correct
16 Correct 2725 ms 18560 KB Output is correct
17 Correct 309 ms 11280 KB Output is correct
18 Correct 1810 ms 14576 KB Output is correct