oj.uz

Submission #601078

# Submission time Handle Problem Language Result Execution time Memory
601078 2022-07-21T10:55:54 Z codr0 Synchronization (JOI13_synchronization) C++14
100 / 100
 4203 ms 113712 KB 
// Code by Parsa Eslami
     
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>

#define bit(i,j) ((j>>i)&1)
#define minm(x,y) x=min(x,y)
#define maxm(x,y) x=max(x,y)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n'
#define wtf cout<<"WHAT THE FUCK!\n"
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1

using namespace std;
const int N=2e5+4;
int S[N],seg[2][4*N],lazy[4*N];
vector<pair<int,pii>> adj[N];
vector<int> vc[N];
bool hide[N];
vector<pii> his[N];
int ans[N];
int n,m;

	void undo(int x){
		while(!his[x].empty()){
			pii w=his[x].back();
			his[x].pop_back();
			if(w.F<0) lazy[-w.F]=w.S;
			else seg[w.F&1][w.F/2]=w.S;
		}
		his[x].clear();
	}

	void _(int id,int x,int h,bool b){
		assert(h!=0);
		if(h>0) his[h].pb({2*id+b,seg[b][id]});
		seg[b][id]=x;
	}

	void _(int id,int x,int h){
		assert(h!=0);
		if(h>0) his[h].pb({-id,lazy[id]});
		lazy[id]=x;
	}

	void shift(int id,int h){
		if(!lazy[id]) return;
		_(lc,lazy[id],h,1);
		_(lc,lazy[id],h,0);
		_(rc,lazy[id],h,1);
		_(rc,lazy[id],h,0);
		_(lc,lazy[id],h);
		_(rc,lazy[id],h);
		_(id,0,h);
	}

	int bs0(int id,int l,int r,int x,int h){// <=x
		if(seg[0][1]>x) return 0;
		if(l+1==r) return l;
		dmid;
		shift(id,h);
		if(seg[0][rc]<=x) return bs0(rc,mid,r,x,h);
		else return bs0(lc,l,mid,x,h);
	}

	int bs1(int id,int l,int r,int x,int h){// >=x
		if(seg[1][1]<x) return m+1;
		if(l+1==r) return l;
		dmid;
		shift(id,h);
		if(seg[1][lc]>=x) return bs1(lc,l,mid,x,h);
		else return bs1(rc,mid,r,x,h);
	}

	void upd(int id,int l,int r,int st,int en,int x,int h){
		if(st>=r||en<=l) return;
		if(st<=l&&en>=r){
			_(id,x,h,0);
			_(id,x,h,1);
			_(id,x,h);
			return;
		}
		dmid;
		shift(id,h);
		upd(lc,l,mid,st,en,x,h);
		upd(rc,mid,r,st,en,x,h);
		_(id,seg[0][lc],h,0);
		_(id,seg[1][rc],h,1);
	}

	void plant(int v,int p){
		S[v]=SZ(adj[v]);
		FOR(i,0,SZ(adj[v])-1) if((i==0||adj[v][i].F!=adj[v][i-1].F)&&adj[v][i].F!=p&&!hide[adj[v][i].F]){
			int u=adj[v][i].F;
			plant(u,v);
			S[v]+=S[u];
		}
	}

	int find_centroid(int v,int p,int _n){
		FOR(i,0,SZ(adj[v])-1) if((i==0||adj[v][i].F!=adj[v][i-1].F)&&!hide[adj[v][i].F]&&adj[v][i].F!=p&&2*S[adj[v][i].F]>_n) return find_centroid(adj[v][i].F,v,_n);
		return v;
	}

	void dfs1(int v,int p,int h,int a1,int a2){
		int WW=bs0(1,1,m+1,m,h);
		if(WW!=0&&a1!=a2) ans[v]-=(upper_bound(all(vc[a1]),WW)-vc[a1].begin());
		if(WW!=0) ans[v]+=(upper_bound(all(vc[a2]),WW)-vc[a2].begin());
		FOR(i,0,SZ(adj[v])-1) if(adj[v][i].F!=p&&!hide[adj[v][i].F]){
			vector<pii> b;
			int u=adj[v][i].F;
			b.pb(adj[v][i].S);
			while(i!=SZ(adj[v])-1&&adj[v][i+1].F==u){
				i++;
				b.pb(adj[v][i].S);
			}
			FOR(ii,0,SZ(b)-2){
				int l=bs1(1,1,m+1,b[ii].S+1,h+1);
				int r=bs0(1,1,m+1,b[ii+1].F-1,h+1)+1;
				if(r>l) upd(1,1,m+1,l,r,b[ii+1].F,h+1);
			}
			int x=bs0(1,1,m+1,b[0].F-1,h+1)+1;
			if(x>1) upd(1,1,m+1,1,x,b[0].F,h+1);
			x=bs1(1,1,m+1,b.back().S+1,h+1);
			if(x<m+1) upd(1,1,m+1,x,m+1,m+1,h+1);
			if(a1==a2) dfs1(u,v,h+1,u,v);
			else dfs1(u,v,h+1,a1,a2);
			undo(h+1);
		}
	}

	void dfs2(int v,int p,int h,int a1,int a2){
		//cout<<v<<" ";
		int WW=m+1-bs0(1,1,m+1,m,h);
		if(a1!=a2) vc[a1].pb(WW);
		vc[a2].pb(WW);
		FOR(i,0,SZ(adj[v])-1) if(adj[v][i].F!=p&&!hide[adj[v][i].F]){
			vector<pii> b;
			int u=adj[v][i].F;
			b.pb(adj[v][i].S);
			while(i!=SZ(adj[v])-1&&adj[v][i+1].F==u){
				i++;
				b.pb(adj[v][i].S);
			}
			FOR(ii,0,SZ(b)-1) b[ii]={m+1-b[ii].S,m+1-b[ii].F};
			reverse(all(b));
			FOR(ii,0,SZ(b)-2){
				int l=bs1(1,1,m+1,b[ii].S+1,h+1);
				int r=bs0(1,1,m+1,b[ii+1].F-1,h+1)+1;
				if(r>l) upd(1,1,m+1,l,r,b[ii+1].F,h+1);
			}
			int x=bs0(1,1,m+1,b[0].F-1,h+1)+1;
			if(x>1) upd(1,1,m+1,1,x,b[0].F,h+1);
			x=bs1(1,1,m+1,b.back().S+1,h+1);
			if(x<m+1) upd(1,1,m+1,x,m+1,m+1,h+1);
			if(a1==a2) dfs2(u,v,h+1,u,v);
			else dfs2(u,v,h+1,a1,a2);
			undo(h+1);
		}
	}
	

	void decompose(int v){
		plant(v,v);
		v=find_centroid(v,v,S[v]);
		dfs2(v,v,0,v,v);
		/*FOR(i,0,SZ(adj[v])-1) if(i==0||adj[v][i].F!=adj[v][i-1].F){
			int u=adj[v][i].F;
			if(!hide[u]) dfs2(u,u,0,u,v);
		}*/
		sort(all(vc[v]));
		FOR(i,0,SZ(adj[v])-1) if(i==0||adj[v][i].F!=adj[v][i-1].F){
			int u=adj[v][i].F;
			if(!hide[u]) sort(all(vc[u]));
		}
		/*FOR(i,0,SZ(adj[v])-1) if(i==0||adj[v][i].F!=adj[v][i-1].F){
			int u=adj[v][i].F;
			if(!hide[u]) dfs1(u,u,0,u,v);
		}*/
		dfs1(v,v,0,v,v);
		/*cout<<"#"<<v<<'\n';
		if(v==2) FOR(i,1,4) cout<<bs0(1,1,m+1,i,-1)<<" ";
		cout<<'\n';
		int cc[2]={v,3};
		FOR(I,0,1){
			int i=cc[I];
			for(int wu:vc[i]) cout<<wu<<" ";
			cout<<'\n';
		}
		cout<<ans[3]<<'\n';*/
		hide[v]=1;
		vc[v].clear();
		vc[v].shrink_to_fit();
		FOR(i,0,SZ(adj[v])-1) if(i==0||adj[v][i].F!=adj[v][i-1].F){
			int u=adj[v][i].F;
			if(!hide[u]){
				vc[u].clear();
				vc[u].shrink_to_fit();
				decompose(u);
			}
		}
	}

	int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int q; cin>>n>>m>>q;
	pii E[n];
	FOR(i,1,n-1) cin>>E[i].F>>E[i].S;
	map<int,int> mp;
	FOR(i,1,m){
		int w; cin>>w;
		if(mp[w]){
			int l=mp[w];
			int r=i;
			mp[w]=0;
			int u=E[w].F;
			int v=E[w].S;
			adj[u].pb({v,{l,r}});
			adj[v].pb({u,{l,r}});
		}else mp[w]=i;
	}
	for(pii x0:mp) if(x0.S!=0){
		int l=x0.S;
		int r=m;
		int u=E[x0.F].F;
		int v=E[x0.F].S;
		adj[u].pb({v,{l,r}});
		adj[v].pb({u,{l,r}});
	}
	FOR(i,1,m) upd(1,1,m+1,i,i+1,i,-1);
	FOR(i,1,n) sort(all(adj[i]));
	FOR(i,1,n) if(!hide[i]) decompose(i);
	while(q--){
		int v; cin>>v; cout<<ans[v]<<'\n';
	}

	return 0;
	}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 10 ms 14456 KB Output is correct
3 Correct 10 ms 14420 KB Output is correct
4 Correct 9 ms 14376 KB Output is correct
5 Correct 11 ms 14420 KB Output is correct
6 Correct 19 ms 14572 KB Output is correct
7 Correct 193 ms 16552 KB Output is correct
8 Correct 181 ms 16540 KB Output is correct
9 Correct 203 ms 16588 KB Output is correct
10 Correct 2514 ms 33864 KB Output is correct
11 Correct 2312 ms 33876 KB Output is correct
12 Correct 1551 ms 33836 KB Output is correct
13 Correct 907 ms 35664 KB Output is correct
14 Correct 2105 ms 30864 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2807 ms 95992 KB Output is correct
2 Correct 2711 ms 95924 KB Output is correct
3 Correct 4142 ms 111668 KB Output is correct
4 Correct 4173 ms 111808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14432 KB Output is correct
6 Correct 17 ms 14548 KB Output is correct
7 Correct 119 ms 16500 KB Output is correct
8 Correct 1507 ms 34516 KB Output is correct
9 Correct 1657 ms 34476 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1657 ms 33492 KB Output is correct
2 Correct 4144 ms 113712 KB Output is correct
3 Correct 4147 ms 112728 KB Output is correct
4 Correct 4197 ms 112492 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 10 ms 14424 KB Output is correct
5 Correct 23 ms 14572 KB Output is correct
6 Correct 182 ms 16608 KB Output is correct
7 Correct 2312 ms 34536 KB Output is correct
8 Correct 1535 ms 34604 KB Output is correct
9 Correct 930 ms 36740 KB Output is correct
10 Correct 2149 ms 31928 KB Output is correct
11 Correct 2764 ms 97868 KB Output is correct
12 Correct 2753 ms 97792 KB Output is correct
13 Correct 4203 ms 112720 KB Output is correct