Submission #995359

#	Time	Username	Problem	Language	Result	Execution time	Memory
995359		vjudge1	Synchronization (JOI13_synchronization)	C++17	0 / 100	168 ms	262144 KiB

synchronization

#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a:b)
#define ll long long
#define pb push_back
#define endl "\n"
#define pii pair<int, int>
#define fi first
#define se second
#define mid ((l+r)>>1)

using namespace std;

struct segtree{
	segtree *left, *right;
	int l, r, v=0;
	segtree(int x, int y): l(x), r(y){
		if(l==r) return;
		left = new segtree(l,mid);
		right= new segtree(mid+1,r);
	}
	void update(int x){
		if(r<x || x<l) return;
		if(x<=l && r<=x){
			v^=1;
			return;
		}
		left->update(x);
		right->update(x);
		v=((left->v)&(right->v));
	}
	int query(int x, int y){
		if(r<x || y<l) return 1;
		if(x<=l && r<=y) return v;
		return ((left->query(x,y))&(right->query(x,y)));
	}
};

const int lim=1e5+2;
int sz[lim], tin[lim], root[lim], par[lim], hvy[lim], node[lim], timer;
vector<int> adj[lim];
bitset<lim> vnode[lim];
segtree ST(0,lim);

void sztree(int u, int p){
	sz[u]=1;
	hvy[u]=lim-1;
	par[u]=p;
	repa(v,adj[u]){
		if(v==p) continue;
		sztree(v,u);
		sz[u]+=sz[v];
		if(sz[hvy[u]]<sz[v]) hvy[u]=v;
	}
}

void dfs_hld(int u, int p){
	tin[u]=timer++;
	node[tin[u]]=u;
	repa(v,adj[u]){
		if(v!=hvy[u]) continue;
		root[v]=root[u];
		dfs_hld(v,u);
	}
	repa(v,adj[u]){
		if(v==hvy[u] || v==p) continue;
		root[v]=v;
		dfs_hld(v,u);
	}
}

int query(int u){
	while(ST.query(tin[root[u]],tin[u])) u=par[u];
	//PINCHE BINARIA COMO NO ME SALGA ME PEGO UN TIRO
	int l, r;
	l=tin[root[u]],r=tin[u];
	while(l<=r){
		if(ST.query(mid,r)) r=mid-1;
		else l=mid+1;
	}
	if(r<tin[u]) return node[r];
	else return u;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m, q, u, v;
	cin>>n>>m>>q;
	pii edges[n];
	rep(i,1,n+1) vnode[i].set(i);
	rep(i,1,n){
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
		edges[i]={u,v};
	}
	sztree(1,0);
	rep(i,1,n) if(par[edges[i].fi]!=edges[i].se) swap(edges[i].fi,edges[i].se);
	root[1]=1;
	dfs_hld(1,0);
	while(m--){
		cin>>u;
		u=edges[u].fi;
		v=query(u);
		if(v!=u) vnode[u]|=vnode[v];
		ST.update(tin[u]);
		v=query(u);
		if(v!=u) vnode[v]|=vnode[u];
	}
	while(q--){
		cin>>u;
		v=query(u);
		if(v!=u) vnode[u]|=vnode[v];
		cout<<vnode[u].count()<<endl;
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40