oj.uz

Submission #397157

# Submission time Handle Problem Language Result Execution time Memory
397157 2021-05-01T15:46:02 Z keta_tsimakuridze Synchronization (JOI13_synchronization) C++14
100 / 100
 491 ms 29592 KB 
#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,cnt[N],pos[N],ind[N],cur,n,m,q,u[N],v[N],bef[N],par[N],sz[N],st[N],ch[N],idx,f[N];
vector<int>V[N];
pair<int,int> tree[4*N];
string s;
void update(int u,int ind,int l,int r,int val){
	if(l>ind || r<ind) return;
	if(l==r) {
		tree[u]={val,l};
		return;
	}
	int mid=(l+r)/2;
	update(2*u,ind,l,mid,val);
	update(2*u+1,ind,mid+1,r,val);
	tree[u]=max(tree[2*u],tree[2*u+1]);
}
pair<int,int> getans(int u,int start,int end,int l,int r){
	if(l>end || r<start) return {0,0};
	if(start<=l && r<=end) return tree[u];
	int mid=(l+r)/2;
	return max( getans(2*u,start,end,l,mid),getans(2*u+1,start,end,mid+1,r) );
}
void get_sz(int u,int p){
	sz[u] = 1;
	cnt[u] = 1;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]!=p) get_sz(V[u][i],u),par[V[u][i]]=u,sz[u]+=sz[V[u][i]];
	}
}
void dfs(int u,int p){
	if(!st[cur]) st[cur]=u;
	ch[u] = cur;
	idx++;
	update(1,idx,1,n,1);
	pos[idx] = u;
	ind[u] = idx;
	int mx=0,v=0;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]!=p && sz[V[u][i]]>mx) mx=sz[V[u][i]],v=V[u][i];
	}
	if(v) dfs(v,u);
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]!=p && V[u][i]!=v){
			cur++;
			dfs(V[u][i],u);
		}
	}
}
int get(int u) {
	while(u!=1) {
		pair<int,int> g = getans(1,ind[st[ch[u]]],ind[u],1,n);
		if(g.f == 1){
		return pos[g.s]; }
		u = par[st[ch[u]]];
	}
}
void remove(int u){ 
	int root=get(u);
	update(1,ind[u],1,n,1);
	
	bef[u] = cnt[root];
	cnt[u] = cnt[root];
}
void add(int u) {
	update(1,ind[u],1,n,0); 
	int root = get(u);
	cnt[root]+=cnt[u] - bef[u];
}
 main(){
	// t=1;
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<n;i++){
		cin>>u[i]>>v[i];
		V[v[i]].push_back(u[i]);
		V[u[i]].push_back(v[i]);
	}
	get_sz(1,0);
	cur=1;
	dfs(1,0);
	for(int i=1;i<=m;i++){
		int ind;
		cin>>ind;
		if(sz[v[ind]]>sz[u[ind]]) swap(v[ind],u[ind]);
		if(f[ind]) remove(v[ind]),f[ind]=0;
		else add(v[ind]),f[ind]=1;
	}
	for(int i=1;i<=q;i++){
		int u;
		cin >> u;
		cout<<cnt[get(u)]<<" ";
	}
}

Compilation message

synchronization.cpp: In function 'void get_sz(long long int, long long int)':
synchronization.cpp:31:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
synchronization.cpp: In function 'void dfs(long long int, long long int)':
synchronization.cpp:43:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
synchronization.cpp:47:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
synchronization.cpp: At global scope:
synchronization.cpp:74:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 |  main(){
      |       ^
synchronization.cpp: In function 'long long int get(long long int)':
synchronization.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 5028 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5036 KB Output is correct
6 Correct 5 ms 5196 KB Output is correct
7 Correct 26 ms 6976 KB Output is correct
8 Correct 26 ms 7000 KB Output is correct
9 Correct 26 ms 6988 KB Output is correct
10 Correct 430 ms 23364 KB Output is correct
11 Correct 425 ms 23424 KB Output is correct
12 Correct 279 ms 28896 KB Output is correct
13 Correct 314 ms 23536 KB Output is correct
14 Correct 269 ms 22020 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 25336 KB Output is correct
2 Correct 167 ms 25172 KB Output is correct
3 Correct 124 ms 27324 KB Output is correct
4 Correct 124 ms 27332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5028 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 24 ms 7588 KB Output is correct
8 Correct 304 ms 29380 KB Output is correct
9 Correct 311 ms 29592 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 29448 KB Output is correct
2 Correct 160 ms 28368 KB Output is correct
3 Correct 162 ms 28560 KB Output is correct
4 Correct 164 ms 28524 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 6 ms 5268 KB Output is correct
6 Correct 32 ms 7048 KB Output is correct
7 Correct 491 ms 24260 KB Output is correct
8 Correct 328 ms 29500 KB Output is correct
9 Correct 426 ms 24648 KB Output is correct
10 Correct 443 ms 23272 KB Output is correct
11 Correct 201 ms 26544 KB Output is correct
12 Correct 218 ms 26668 KB Output is correct
13 Correct 161 ms 28484 KB Output is correct