Submission #644865

#	Time	Username	Problem	Language	Result	Execution time	Memory
644865		ono_de206	Synchronization (JOI13_synchronization)	C++14	100 / 100	488 ms	23616 KiB

synchronization

#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

const int mxn=2e5+10;
int n;
int in[mxn],out[mxn],sub[mxn],dth[mxn],par[mxn],anc[mxn];

int is[mxn];

vector<int> g[mxn];

int d[mxn*4],seg[mxn];

int ans[mxn],alr[mxn];

void dfs1(int to,int fr)
{
	sub[to]=1;
	par[to]=fr;
	ans[to]=1;
	for(int x : g[to])
	{
		if(x==fr) continue;
		dfs1(x,to);
		sub[to]+=sub[x];
	}
}

int t;

void dfs2(int to,int top)
{
	t++;
	in[to]=t;
	seg[t]=to;
	anc[to]=top;
	int mx=-1,idx=-1;
	for(int x : g[to])
	{
		if(x==par[to]) continue;
		if(sub[x]>mx)
		{
			mx=sub[x];
			idx=x;
		}
	}
	if(idx==-1)
	{
		out[to]=t;
		return;
	}
	dfs2(idx,top);
	for(int x : g[to])
	{
		if(x==par[to] || x==idx) continue;
		dfs2(x,x);
	}
	out[to]=t;
}

void build(int l,int r,int i)
{
	if(l==r)
	{
		d[i]=1;
		return;
	}
	int m=(l+r)/2;
	build(l,m,i*2);
	build(m+1,r,i*2+1);
	d[i]=d[i*2]+d[i*2+1];
}

void update(int l,int r,int i,int x)
{
	if(l==r)
	{
		d[i]^=1;
		return;
	}
	int m=(l+r)/2;
	if(x>m) update(m+1,r,i*2+1,x);
	if(x<=m) update(l,m,i*2,x);
	d[i]=d[i*2+1]+d[i*2];
}

int sum(int l,int r,int i,int x,int y)
{
	if(l>y || r<x) return 0;
	if(l>=x && r<=y) return d[i];
	int m=(l+r)/2;
	return sum(l,m,i*2,x,y)+sum(m+1,r,i*2+1,x,y);
}

int query(int l,int r,int i,int x,int y)
{
	if(l==r) 
	{
		if(d[i]==1) return seg[l];
		else return -1;
	}
	int m=(l+r)/2;
	if(y<=m) return query(l,m,i*2,x,y);
	if(x>m) return query(m+1,r,i*2+1,x,y);
	int tmp=sum(1,n,1,m+1,y);
	if(tmp) return query(m+1,r,i*2+1,x,y);
	else return query(l,m,i*2,x,y);
}

int get_anc(int x)
{
	while(1)
	{
		int tmp=sum(1,n,1,in[anc[x]],in[x]);
		if(tmp==0)
		{
			x=par[anc[x]];
			continue;
		}
		return query(1,n,1,in[anc[x]],in[x]);
	}
	return -1;
}

int main()
{
	fast;
	int m,q;
	cin>>n>>m>>q;
	vector<pair<int,int>> edge;
	for(int i=2; i<=n; i++)
	{
		int x,y;
		cin>>x>>y;
		edge.pb({x,y});
		g[x].pb(y);
		g[y].pb(x);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,n,1);
	for(int i=1; i<=m; i++)
	{
		int x;
		cin>>x;
		x--;
		if(par[edge[x].ss]==edge[x].ff) swap(edge[x].ss,edge[x].ff);
		if(is[x]==1)
		{
			int ances=get_anc(edge[x].ss);
			alr[edge[x].ff]=ans[edge[x].ff]=ans[ances];
			update(1,n,1,in[edge[x].ff]);
		}
		else
		{
			int ances=get_anc(edge[x].ss);
			ans[ances]+=ans[edge[x].ff]-alr[edge[x].ff];
			update(1,n,1,in[edge[x].ff]);
		}
		is[x]^=1;
	}
	for(;q--;)
	{
		int x;
		cin>>x;
		cout<<ans[get_anc(x)]<<'\n';
	}
	return 0;
}

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