oj.uz

Submission #601091

# Submission time Handle Problem Language Result Execution time Memory
601091 2022-07-21T11:03:37 Z codr0 Synchronization (JOI13_synchronization) C++14
100 / 100
 3530 ms 120808 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&&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 7 ms 14420 KB Output is correct
2 Correct 7 ms 14396 KB Output is correct
3 Correct 7 ms 14456 KB Output is correct
4 Correct 8 ms 14396 KB Output is correct
5 Correct 8 ms 14480 KB Output is correct
6 Correct 15 ms 14548 KB Output is correct
7 Correct 129 ms 16884 KB Output is correct
8 Correct 122 ms 16716 KB Output is correct
9 Correct 131 ms 16764 KB Output is correct
10 Correct 1696 ms 36692 KB Output is correct
11 Correct 1653 ms 36516 KB Output is correct
12 Correct 1123 ms 35040 KB Output is correct
13 Correct 728 ms 34320 KB Output is correct
14 Correct 1557 ms 36824 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2066 ms 99924 KB Output is correct
2 Correct 2131 ms 98760 KB Output is correct
3 Correct 3445 ms 118696 KB Output is correct
4 Correct 3530 ms 118912 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 14416 KB Output is correct
4 Correct 8 ms 14408 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 16 ms 14644 KB Output is correct
7 Correct 107 ms 16640 KB Output is correct
8 Correct 1304 ms 35268 KB Output is correct
9 Correct 1201 ms 35408 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1158 ms 35276 KB Output is correct
2 Correct 2938 ms 120808 KB Output is correct
3 Correct 3040 ms 119044 KB Output is correct
4 Correct 2981 ms 119356 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 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 16 ms 14624 KB Output is correct
6 Correct 133 ms 16824 KB Output is correct
7 Correct 1738 ms 36952 KB Output is correct
8 Correct 1157 ms 35364 KB Output is correct
9 Correct 747 ms 34604 KB Output is correct
10 Correct 1593 ms 37316 KB Output is correct
11 Correct 2039 ms 100424 KB Output is correct
12 Correct 2017 ms 100316 KB Output is correct
13 Correct 3045 ms 119232 KB Output is correct