Submission #906325

#	Time	Username	Problem	Language	Result	Execution time	Memory
906325		Belphegor	오두막집 (GA7_cabana)	C++14	19 / 100	6037 ms	18040 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 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 (stderr)

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 / 7
• Subtask 2: 0 / 23
• Subtask 3: 12 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37