oj.uz

Submission #601087

# Submission time Handle Problem Language Result Execution time Memory
601087 2022-07-21T11:01:24 Z codr0 Synchronization (JOI13_synchronization) C++14
100 / 100
 4313 ms 112864 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){
		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);
		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]));
		}
		dfs1(v,v,0,v,v);
		hide[v]=1;
		vc[v].clear();
		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();
				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 14464 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 19 ms 14632 KB Output is correct
7 Correct 175 ms 16764 KB Output is correct
8 Correct 177 ms 16776 KB Output is correct
9 Correct 180 ms 16804 KB Output is correct
10 Correct 2373 ms 36648 KB Output is correct
11 Correct 2296 ms 36472 KB Output is correct
12 Correct 1476 ms 35056 KB Output is correct
13 Correct 945 ms 34236 KB Output is correct
14 Correct 2252 ms 36532 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2923 ms 95764 KB Output is correct
2 Correct 2897 ms 94932 KB Output is correct
3 Correct 4313 ms 110712 KB Output is correct
4 Correct 4196 ms 111100 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14400 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 10 ms 14472 KB Output is correct
4 Correct 8 ms 14412 KB Output is correct
5 Correct 10 ms 14420 KB Output is correct
6 Correct 16 ms 14680 KB Output is correct
7 Correct 120 ms 16680 KB Output is correct
8 Correct 1509 ms 35200 KB Output is correct
9 Correct 1472 ms 35208 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1497 ms 35220 KB Output is correct
2 Correct 3994 ms 112864 KB Output is correct
3 Correct 4077 ms 111220 KB Output is correct
4 Correct 4109 ms 111324 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14356 KB Output is correct
2 Correct 10 ms 14456 KB Output is correct
3 Correct 10 ms 14420 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 21 ms 14676 KB Output is correct
6 Correct 187 ms 16820 KB Output is correct
7 Correct 2514 ms 36968 KB Output is correct
8 Correct 1702 ms 35304 KB Output is correct
9 Correct 1061 ms 34684 KB Output is correct
10 Correct 2265 ms 37388 KB Output is correct
11 Correct 2754 ms 96416 KB Output is correct
12 Correct 2750 ms 96452 KB Output is correct
13 Correct 4110 ms 111216 KB Output is correct