Submission #1106928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106928		PieArmy	Synchronization (JOI13_synchronization)	C++17	20 / 100	75 ms	17736 KiB

synchronization

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

int n,m,q;
vector<pair<int,int>>komsu[100001];
int fir[100001],las[100001],tip[100001],sub[100001],ans[100001];

void dfs(int pos,int par){
	sub[pos]=1;
	for(pair<int,int>x:komsu[pos]){
		if(sub[x.fr]==-1)continue;
		if(x.fr==par)continue;
		dfs(x.fr,pos);
		sub[pos]+=sub[x.fr];
	}
}

void deco(int pos){
	dfs(pos,pos);
	int total=sub[pos];
	while(true){
		int nex=-1;
		for(auto x:komsu[pos]){
			if(sub[x.fr]==-1)continue;
			if(sub[x.fr]>sub[pos])continue;
			if(sub[x.fr]>total/2){
				nex=x.fr;
				break;
			}
		}
		if(nex==-1)break;
		pos=nex;
	}
	sub[pos]=-1;
	ans[pos]++;
	sort(komsu[pos].begin(),komsu[pos].end(),[&](const pair<int,int>&x,const pair<int,int>&y){
		if((sub[x.fr]==-1)==(sub[y.fr]==-1))return fir[x.sc]<fir[y.sc];
		return sub[x.fr]>sub[y.fr];
	});
	vector<int>pref;
	bool b=false;
	for(auto x:komsu[pos]){
		if(sub[x.fr]==-1)b=true;
		else if(fir[x.sc]==sonsuz)b=true;
		else if(b){
			assert(0);
		}
		if(b)continue;
		pref.pb(0);
		queue<pair<int,int>>q;
		q.push(x);
		while(q.size()){
			int loc=q.front().fr,prev=q.front().sc;
			q.pop();
			ans[pos]++;
			pref.back()++;
			for(auto y:komsu[loc]){
				if(sub[y.fr]==-1)continue;
				if(y.sc==prev)continue;
				if(fir[y.sc]<=las[prev]){
					q.push(y);
				}
			}
		}
	}
	for(int i=1;i<pref.size();i++){
		pref[i]+=pref[i-1];
	}

	for(int i=0;i<komsu[pos].size();i++){
		pair<int,int>x=komsu[pos][i];
		if(sub[x.fr]==-1)break;
		if(fir[x.sc]==sonsuz)break;
		int l=0,r=pref.size()-1;
		while(l<r){
			if(fir[komsu[pos][(l+r+1)/2].sc]<=las[x.sc])l=(l+r+1)/2;
			else r=((l+r+1)/2)-1;
		}
		queue<pair<int,int>>q;
		q.push(x);
		while(q.size()){
			int loc=q.front().fr,prev=q.front().sc;
			q.pop();
			ans[loc]+=pref[l]-pref[i]+(i==0?0:pref[i-1])+1;
			for(auto y:komsu[loc]){
				if(sub[y.fr]==-1)continue;
				if(y.sc==prev)continue;
				if(fir[prev]<=las[y.sc]){
					q.push(y);
				}
			}
		}
	}
	
	for(auto x:komsu[pos]){
		if(sub[x.fr]==-1)continue;
		deco(x.fr);
	}
}

void code(){
	cin>>n>>m>>q;
	fir[0]=0;
	las[0]=sonsuz-1;
	for(int i=1;i<n;i++){
		fir[i]=sonsuz;
		las[i]=-1;
		int x,y;cin>>x>>y;
		komsu[x].pb({y,i});
		komsu[y].pb({x,i});
	}
	for(int i=1;i<=m;i++){
		int x;cin>>x;
		tip[x]^=1;
		if(tip[x]==0){
			las[x]=i-1;
		}
		else if(fir[x]==sonsuz){
			fir[x]=i;
		}
	}
	for(int i=1;i<n;i++){
		if(tip[i]==1)las[i]=m;
	}
	deco(1);
	while(q--){
		int x;cin>>x;
		cout<<ans[x]<<endl;
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
	int t=1;
	if(!t)cin>>t;
	while(t--){code();cout<<endl;}
	return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'void deco(int)':
synchronization.cpp:76:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i=1;i<pref.size();i++){
      |              ~^~~~~~~~~~~~
synchronization.cpp:80:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i=0;i<komsu[pos].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:144:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:144:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40