oj.uz

Submission #601094

# Submission time Handle Problem Language Result Execution time Memory
601094 2022-07-21T11:06:00 Z codr0 Synchronization (JOI13_synchronization) C++14
100 / 100
 3252 ms 120632 KB 
// Code by Parsa Eslami
     
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#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) return;
		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(WW==m+1) return;
		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 7 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 14372 KB Output is correct
6 Correct 16 ms 14632 KB Output is correct
7 Correct 115 ms 16628 KB Output is correct
8 Correct 117 ms 16824 KB Output is correct
9 Correct 122 ms 16716 KB Output is correct
10 Correct 1563 ms 35740 KB Output is correct
11 Correct 1527 ms 35836 KB Output is correct
12 Correct 1112 ms 34728 KB Output is correct
13 Correct 741 ms 34312 KB Output is correct
14 Correct 1662 ms 36740 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2143 ms 99808 KB Output is correct
2 Correct 2003 ms 99016 KB Output is correct
3 Correct 3044 ms 118536 KB Output is correct
4 Correct 3237 ms 118912 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 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 9 ms 14484 KB Output is correct
6 Correct 18 ms 14644 KB Output is correct
7 Correct 96 ms 16600 KB Output is correct
8 Correct 1251 ms 34840 KB Output is correct
9 Correct 1223 ms 34960 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1219 ms 34892 KB Output is correct
2 Correct 3252 ms 120632 KB Output is correct
3 Correct 3099 ms 119080 KB Output is correct
4 Correct 3091 ms 119044 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14408 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 17 ms 14640 KB Output is correct
6 Correct 130 ms 16756 KB Output is correct
7 Correct 1568 ms 35996 KB Output is correct
8 Correct 1114 ms 34892 KB Output is correct
9 Correct 752 ms 34580 KB Output is correct
10 Correct 1598 ms 37360 KB Output is correct
11 Correct 2057 ms 100328 KB Output is correct
12 Correct 2036 ms 100320 KB Output is correct
13 Correct 3081 ms 119060 KB Output is correct