Submission #239606

#	Time	Username	Problem	Language	Result	Execution time	Memory
239606		kshitij_sodani	Synchronization (JOI13_synchronization)	C++17	100 / 100	534 ms	24680 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second

int n,m,q;
vector<int> adj[100001];
int par[100001][20];
int st[100001];
int endd[100001];
int co=0;
void dfs(int no,int par2=-1){
	par[no][0]=par2;
	co+=1;
	st[no]=co;
	for(auto j:adj[no]){
		if(j!=par2){
			dfs(j,no);
		}
	}
	endd[no]=co;
}
int tree[100010];
int cc[100001];
int dd[100001];
int vis[100001];
void u(int i,int j){
	while(i<100010){
		tree[i]+=j;
		i+=(i&-i);
	}
}
int s(int i){
	int tot=0;
	while(i>0){
		tot+=tree[i];
		i-=(i&-i);
	}
	return tot;
}
int find(int no){
	if(no==0){
		return no;
	}
	int x=s(st[no]);
	if(x-s(st[par[no][0]])>0){
		return no;
	}
	for(int i=19;i>=0;i--){
		if(par[no][i]==-1){
			continue;
		}
		if(par[no][i]==0){
			continue;
		}
		else{
			if(x-s(st[par[par[no][i]][0]])==0){
				no=par[no][i];
			}
		}
	}
	return par[no][0];
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m>>q;
	vector<pair<int,int>> ed;
	for(int i=0;i<n-1;i++){
		int aa,bb;
		cin>>aa>>bb;
		adj[aa-1].pb(bb-1);
		adj[bb-1].pb(aa-1);
		ed.pb({aa-1,bb-1});
	}
	dfs(0);
	for(int i=0;i<ed.size();i++){
		if(par[ed[i].a][0]==ed[i].b){
			swap(ed[i].a,ed[i].b);
		}
	}
	for(int i=0;i<n;i++){
		cc[i]=1;
		dd[i]=0;
	}
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(par[i][j-1]==-1){
				par[i][j]=-1;
			}
			else{
				par[i][j]=par[par[i][j-1]][j-1];
			}
		}
	}	
	for(int i=0;i<n;i++){
		u(st[i],1);
		u(endd[i]+1,-1);
	}
	/*for(int j=0;j<5;j++){
			cout<<s(j+1)<<" ";
		}
		cout<<endl;*/
	for(int i=0;i<m;i++){
		int aa;
		cin>>aa;
		aa--;
		if(vis[aa]==0){			
			int x=find(ed[aa].a);
		//	cout<<x<<"::"<<endl;
			int ne=cc[x]+cc[ed[aa].b]-dd[ed[aa].b];
			cc[x]=ne;
			u(st[ed[aa].b],-1);
			u(endd[ed[aa].b]+1,1);
		}
		else{
			int x=find(ed[aa].a);
		//	cout<<x<<",,"<<endl;

			dd[ed[aa].b]=cc[x];
			cc[ed[aa].b]=cc[x];

			u(st[ed[aa].b],1);
			u(endd[ed[aa].b]+1,-1);
		}
		/*for(int j=0;j<5;j++){
			cout<<s(j+1)<<" ";
		}
		cout<<endl;*/
		vis[aa]=1-vis[aa];
	}
	for(int i=0;i<q;i++){
		int aa;
		cin>>aa;
		aa--;
		int x=find(aa);
//		cout<<x<<"/"<<endl;
		cout<<cc[x]<<endl;//<<":"<<endl;;
	}
//	cout<<st[4]<<endl;
	//cout<<s(4)<<endl;



	return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ed.size();i++){
              ~^~~~~~~~~~

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