제출 #73781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73781		zscoder	동기화 (JOI13_synchronization)	C++17	100 / 100	361 ms	68756 KiB

synchronization

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int h[111111];
int in[111111];
int out[111111];
int st[111111*4];
vi adj[111111];
bool state[111111];
int timer;
vi lst;
int siz[111111];
int las[111111];

void dfs(int u, int p)
{
	in[u]=++timer; lst.pb(u);
	for(int v:adj[u])
	{
		if(v==p) continue;
		h[v]=h[u]+1; dfs(v,u);
	}
	out[u]=timer;
}

void build(int id, int l, int r)
{
	if(r-l<2)
	{
		st[id]=out[lst[l]];
		return ;
	}
	int mid=(l+r)>>1;
	build(id*2,l,mid); build(id*2+1,mid,r); st[id]=max(st[id*2],st[id*2+1]);
}

void update(int id, int l, int r, int pos, int v)
{
	//cerr<<id<<' '<<l<<' '<<r<<'\n';
	if(pos>=r||pos<l) return ;
	if(r-l<2)
	{
		st[id]=v; return ;
	}
	int mid=(l+r)>>1;
	update(id*2,l,mid,pos,v); update(id*2+1,mid,r,pos,v);
	st[id]=max(st[id*2],st[id*2+1]);
}

int find_current_root(int id, int l, int r, int ql, int qr)
{
	if(l>ql||st[id]<qr) return -1;
	if(r-l<2) return lst[l];
	int mid=(l+r)>>1;
	int r2 = find_current_root(id*2+1,mid,r,ql,qr); if(r2!=-1) return r2;
	return find_current_root(id*2,l,mid,ql,qr);
}
ii edges[111111];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	timer=-1;
	int n,m,q; cin>>n>>m>>q;
	for(int i=0;i<n-1;i++)
	{
		int u,v; cin>>u>>v; u--; v--;
		adj[u].pb(v); adj[v].pb(u); edges[i]=mp(u,v);
	}
	for(int i=0;i<n;i++) siz[i]=1;
	dfs(0,-1); 
	build(1,0,n);
	for(int i=0;i<n-1;i++)
	{
		if(h[edges[i].fi]>h[edges[i].se]) swap(edges[i].fi,edges[i].se);
	}
	for(int i=0;i<m;i++)
	{
		int x; cin>>x; x--;
		int u=edges[x].fi; int v=edges[x].se; int rt = find_current_root(1,0,n,in[u],out[u]);
		//cerr<<u<<' '<<v<<' '<<rt<<'\n';
		if(!state[x])
		{
			siz[rt]+=siz[v]-las[v]; //v must be root 
			update(1,0,n,in[v],-1);
		}
		else
		{
			siz[v]=siz[rt];
			las[v]=siz[rt];
			update(1,0,n,in[v],out[v]);
		}
		state[x]^=1;
	}
	for(int i=0;i<q;i++)
	{
		int x; cin>>x; x--;
		x=find_current_root(1,0,n,in[x],out[x]);
		cout<<siz[x]<<'\n';
	}
}	

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