oj.uz

Submission #906325

# Submission time Handle Problem Language Result Execution time Memory
906325 2024-01-14T02:30:42 Z Belphegor 오두막집 (GA7_cabana) C++14
19 / 100
 6000 ms 18040 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 fenwick[sz+5],sub[sz+5];
ll dist[sz+5];
ll D,paths;
vector<ll>vals;
vector<int>tmp;
void init(int i){
	while(i<=vals.size()-1){
		fenwick[i] = 0;
		i+=(i&-i);
	}
}
void update(int i,int val){
	while(i<=vals.size()-1){
		fenwick[i]+=val;
		i+=(i&-i);
	}
}
int sum(int i){
	int r = 0;
	while(i){
		r+=fenwick[i];
		i-=(i&-i);
	}
	return r;
}
void DFS(int cur,int par){
	if(cabin[cur]) 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);
	}
}
void DFS2(int cur,int par){
	if(cabin[cur]){
		int id = (int)(lower_bound(vals.begin(),vals.end(),dist[cur])-vals.begin());
		tmp.emplace_back(id);
		int lim = D - dist[cur];
		if(dist[cur] <= D){
			int ID = (int)(upper_bound(vals.begin(),vals.end(),D-dist[cur])-vals.begin());
			paths+=sum(ID-1);
		}
	}
	for(pi p : tree[cur]){
		int nxt = p.first,w = p.second;
		if(v[nxt] || nxt == par) continue;
		DFS2(nxt,cur);
	}
}
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 = {-1}; dist[cent] = 0;
	DFS(cent,0);
	sort(vals.begin(),vals.end());
	vals.erase(unique(vals.begin(),vals.end()),vals.end());
	if(cabin[cent]) update(1,1);
	for(pi p : tree[cent]){
		int nxt = p.first,w = p.second;
		if(v[nxt]) continue;
		tmp.clear();
		DFS2(nxt,cent);
		for(int x : tmp) update(x,1);
	}
	for(int i=1; i<=vals.size(); i++) init(i);
	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] = fenwick[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 'void init(int)':
cabana.cpp:14:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  while(i<=vals.size()-1){
      |        ~^~~~~~~~~~~~~~~
cabana.cpp: In function 'void update(int, int)':
cabana.cpp:20:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  while(i<=vals.size()-1){
      |        ~^~~~~~~~~~~~~~~
cabana.cpp: In function 'void DFS2(int, int)':
cabana.cpp:46:7: warning: unused variable 'lim' [-Wunused-variable]
   46 |   int lim = D - dist[cur];
      |       ^~~
cabana.cpp:53:21: warning: unused variable 'w' [-Wunused-variable]
   53 |   int nxt = p.first,w = p.second;
      |                     ^
cabana.cpp: In function 'void dfs(int, int)':
cabana.cpp:61:21: warning: unused variable 'w' [-Wunused-variable]
   61 |   int nxt = p.first,w = p.second;
      |                     ^
cabana.cpp: In function 'void decomposition(int)':
cabana.cpp:87:21: warning: unused variable 'w' [-Wunused-variable]
   87 |   int nxt = p.first,w = p.second;
      |                     ^
cabana.cpp:93:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(int i=1; i<=vals.size(); i++) init(i);
      |               ~^~~~~~~~~~~~~
cabana.cpp: In function 'int main()':
cabana.cpp:117:45: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  117 |   for(int i=1; i<=n; i++) v[i] = fenwick[i] = 0;
      |                                  ~~~~~~~~~~~^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4956 KB Output is correct
2 Correct 98 ms 5468 KB Output is correct
3 Correct 108 ms 5840 KB Output is correct
4 Correct 431 ms 7260 KB Output is correct
5 Correct 1529 ms 11100 KB Output is correct
6 Correct 5033 ms 14964 KB Output is correct
7 Correct 3597 ms 15700 KB Output is correct
8 Execution timed out 6021 ms 18040 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

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

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4908 KB Output is correct
2 Correct 73 ms 4956 KB Output is correct
3 Correct 326 ms 5904 KB Output is correct
4 Correct 2007 ms 9656 KB Output is correct
5 Correct 901 ms 7280 KB Output is correct
6 Correct 1546 ms 8468 KB Output is correct
7 Correct 1997 ms 9204 KB Output is correct
8 Correct 3575 ms 10064 KB Output is correct
9 Correct 2074 ms 9656 KB Output is correct
10 Correct 3313 ms 10068 KB Output is correct
11 Correct 100 ms 5264 KB Output is correct
12 Correct 2160 ms 9752 KB Output is correct
13 Execution timed out 6037 ms 11300 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4700 KB Output is correct
2 Correct 116 ms 5172 KB Output is correct
3 Correct 109 ms 5460 KB Output is correct
4 Correct 404 ms 5980 KB Output is correct
5 Correct 1857 ms 7576 KB Output is correct
6 Correct 4090 ms 9432 KB Output is correct
7 Correct 4368 ms 9556 KB Output is correct
8 Correct 5640 ms 11220 KB Output is correct
9 Correct 3397 ms 10332 KB Output is correct
10 Execution timed out 6034 ms 11216 KB Time limit exceeded
11 Halted 0 ms 0 KB -