oj.uz

Submission #601126

# Submission time Handle Problem Language Result Execution time Memory
601126 2022-07-21T11:46:34 Z codr0 Synchronization (JOI13_synchronization) C++14
100 / 100
 3060 ms 120720 KB 
// Code by Parsa Eslami
     
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,O3")
#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 14424 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14440 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 17 ms 14548 KB Output is correct
7 Correct 140 ms 16724 KB Output is correct
8 Correct 125 ms 16744 KB Output is correct
9 Correct 126 ms 16724 KB Output is correct
10 Correct 1666 ms 35712 KB Output is correct
11 Correct 1627 ms 35664 KB Output is correct
12 Correct 1160 ms 34616 KB Output is correct
13 Correct 838 ms 34084 KB Output is correct
14 Correct 1627 ms 36724 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2053 ms 99668 KB Output is correct
2 Correct 1985 ms 98788 KB Output is correct
3 Correct 2989 ms 118528 KB Output is correct
4 Correct 3060 ms 119016 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 14388 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14428 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 14 ms 14672 KB Output is correct
7 Correct 91 ms 16624 KB Output is correct
8 Correct 1122 ms 34932 KB Output is correct
9 Correct 1142 ms 35088 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1123 ms 35124 KB Output is correct
2 Correct 2961 ms 120720 KB Output is correct
3 Correct 3020 ms 119116 KB Output is correct
4 Correct 3058 ms 119208 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 14420 KB Output is correct
3 Correct 8 ms 14452 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 15 ms 14676 KB Output is correct
6 Correct 138 ms 16740 KB Output is correct
7 Correct 1573 ms 36048 KB Output is correct
8 Correct 1092 ms 35020 KB Output is correct
9 Correct 767 ms 34704 KB Output is correct
10 Correct 1606 ms 37472 KB Output is correct
11 Correct 2017 ms 100532 KB Output is correct
12 Correct 2059 ms 100436 KB Output is correct
13 Correct 3046 ms 119044 KB Output is correct