oj.uz

Submission #239606

# Submission time Handle Problem Language Result Execution time Memory
239606 2020-06-16T18:21:38 Z kshitij_sodani Synchronization (JOI13_synchronization) C++17
100 / 100
 534 ms 24680 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 16 ms 4352 KB Output is correct
8 Correct 17 ms 4352 KB Output is correct
9 Correct 17 ms 4352 KB Output is correct
10 Correct 188 ms 19180 KB Output is correct
11 Correct 194 ms 19180 KB Output is correct
12 Correct 300 ms 23916 KB Output is correct
13 Correct 96 ms 19044 KB Output is correct
14 Correct 141 ms 18668 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 21352 KB Output is correct
2 Correct 113 ms 21100 KB Output is correct
3 Correct 110 ms 23148 KB Output is correct
4 Correct 109 ms 23148 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 10 ms 2944 KB Output is correct
7 Correct 44 ms 4984 KB Output is correct
8 Correct 534 ms 24632 KB Output is correct
9 Correct 520 ms 24680 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 24552 KB Output is correct
2 Correct 378 ms 24276 KB Output is correct
3 Correct 368 ms 24428 KB Output is correct
4 Correct 375 ms 24428 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 7 ms 2688 KB Output is correct
5 Correct 9 ms 2944 KB Output is correct
6 Correct 38 ms 4480 KB Output is correct
7 Correct 426 ms 20076 KB Output is correct
8 Correct 507 ms 24592 KB Output is correct
9 Correct 306 ms 20420 KB Output is correct
10 Correct 397 ms 19944 KB Output is correct
11 Correct 335 ms 22672 KB Output is correct
12 Correct 339 ms 22504 KB Output is correct
13 Correct 371 ms 24428 KB Output is correct