oj.uz

Submission #1107563

# Submission time Handle Problem Language Result Execution time Memory
1107563 2024-11-01T13:43:44 Z PieArmy Synchronization (JOI13_synchronization) C++17
100 / 100
 137 ms 19448 KB 
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;}

struct Fen{
	int n;
	vector<int>tree,arr;
	void init(int N){
		n=N;
		tree.resize(n+1,0);
		arr.resize(n+1,0);
	}
	void update(int tar){
		int x=((arr[tar]^1)-arr[tar]);
		arr[tar]^=1;
		while(tar<=n){
			tree[tar]+=x;
			tar+=(tar&-tar);
		}
	}
	int qu(int tar){
		int res=0;
		while(tar){
			res+=tree[tar];
			tar-=(tar&-tar);
		}
		return res;
	}
	int query(int l,int r){
		return qu(r)-qu(l-1);
	}
};

int n,m,q;
Fen fen;
int tim=1;
int par[100001],ord[100001],nodes[100001],state[100001],sub[100001],lower[100001],pre[100001];
int ans[100001],old[100001];
vector<pair<int,int>>komsu[100001];

int find_par(int pos){
	while(true){
		if(state[pos]==0){
			return pos;
		}
		if(fen.query(ord[par[pos]],ord[pos])!=ord[pos]-ord[par[pos]]+1){
			int l=ord[par[pos]]+1,r=ord[pos];
			while(l<r){
				int mi=(l+r)/2;
				if(fen.query(mi,ord[pos])==ord[pos]-mi+1){
					r=mi;
				}
				else l=mi+1;
			}
			return pre[nodes[l]];
		}
		pos=pre[par[pos]];
	}
}

void dfs1(int pos){
	sub[pos]=1;
	for(auto x:komsu[pos]){
		if(sub[x.fr])continue;
		lower[x.sc]=x.fr;
		dfs1(x.fr);
		sub[pos]+=sub[x.fr];
	}
}

void dfs2(int pos){
	int mx=-1;
	for(auto x:komsu[pos]){
		if(ord[x.fr])continue;
		if(mx==-1||sub[x.fr]>sub[mx])mx=x.fr;
	}
	if(mx==-1)return;
	ord[mx]=tim++;
	nodes[ord[mx]]=mx;
	pre[mx]=pos;
	par[mx]=par[pos];
	dfs2(mx);
	for(auto x:komsu[pos]){
		if(ord[x.fr])continue;
		ord[x.fr]=tim++;
		pre[x.fr]=pos;
		par[x.fr]=x.fr;
		nodes[ord[x.fr]]=x.fr;
		dfs2(x.fr);
	}
}

void code(){
	cin>>n>>m>>q;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		komsu[x].pb({y,i});
		komsu[y].pb({x,i});
	}
	fen.init(n);
	ord[1]=tim++;
	par[1]=1;
	nodes[ord[1]]=1;
	dfs1(1);
	dfs2(1);
	for(int i=1;i<=n;i++){
		ans[i]=1;
	}
	for(int i=1;i<=m;i++){
		int x;cin>>x;
		x=lower[x];
		if(state[x]==0){
			fen.update(ord[x]);
			state[x]^=1;
			int u=find_par(x);
			ans[u]+=ans[x]-old[x];
			old[x]=ans[x];
		}
		else{
			int u=find_par(x);
			ans[x]=old[x]=ans[u];
			fen.update(ord[x]);
			state[x]^=1;
		}
	}
	for(int i=1;i<=n;i++){
		if(state[i]){
			int u=find_par(i);
			ans[i]=old[i]=ans[u];
			fen.update(ord[i]);
			state[i]^=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

synchronization.cpp: In function 'int main()':
synchronization.cpp:151:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:151:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 1 ms 4688 KB Output is correct
4 Correct 1 ms 4688 KB Output is correct
5 Correct 1 ms 4688 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct
7 Correct 9 ms 5524 KB Output is correct
8 Correct 8 ms 5200 KB Output is correct
9 Correct 7 ms 5200 KB Output is correct
10 Correct 81 ms 12072 KB Output is correct
11 Correct 87 ms 12104 KB Output is correct
12 Correct 118 ms 17748 KB Output is correct
13 Correct 50 ms 12716 KB Output is correct
14 Correct 90 ms 11848 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 15300 KB Output is correct
2 Correct 67 ms 15556 KB Output is correct
3 Correct 88 ms 17992 KB Output is correct
4 Correct 85 ms 17492 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 2 ms 4688 KB Output is correct
4 Correct 1 ms 4688 KB Output is correct
5 Correct 1 ms 4744 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct
7 Correct 11 ms 5968 KB Output is correct
8 Correct 136 ms 19448 KB Output is correct
9 Correct 136 ms 18504 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 18284 KB Output is correct
2 Correct 111 ms 18888 KB Output is correct
3 Correct 113 ms 19344 KB Output is correct
4 Correct 94 ms 19280 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4688 KB Output is correct
2 Correct 1 ms 4688 KB Output is correct
3 Correct 1 ms 4688 KB Output is correct
4 Correct 1 ms 4688 KB Output is correct
5 Correct 2 ms 4688 KB Output is correct
6 Correct 8 ms 5456 KB Output is correct
7 Correct 83 ms 12880 KB Output is correct
8 Correct 129 ms 19068 KB Output is correct
9 Correct 59 ms 13736 KB Output is correct
10 Correct 77 ms 12620 KB Output is correct
11 Correct 83 ms 16436 KB Output is correct
12 Correct 82 ms 15816 KB Output is correct
13 Correct 109 ms 19288 KB Output is correct