oj.uz

Submission #644865

# Submission time Handle Problem Language Result Execution time Memory
644865 2022-09-25T11:42:44 Z ono_de206 Synchronization (JOI13_synchronization) C++14
100 / 100
 488 ms 23616 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5036 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5036 KB Output is correct
6 Correct 4 ms 5176 KB Output is correct
7 Correct 17 ms 6100 KB Output is correct
8 Correct 18 ms 6100 KB Output is correct
9 Correct 18 ms 6116 KB Output is correct
10 Correct 220 ms 15560 KB Output is correct
11 Correct 240 ms 14628 KB Output is correct
12 Correct 354 ms 22752 KB Output is correct
13 Correct 105 ms 15296 KB Output is correct
14 Correct 144 ms 14648 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 19132 KB Output is correct
2 Correct 248 ms 18624 KB Output is correct
3 Correct 203 ms 22360 KB Output is correct
4 Correct 202 ms 22348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5036 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5032 KB Output is correct
6 Correct 5 ms 5176 KB Output is correct
7 Correct 38 ms 7004 KB Output is correct
8 Correct 473 ms 23576 KB Output is correct
9 Correct 487 ms 23084 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 23616 KB Output is correct
2 Correct 393 ms 22820 KB Output is correct
3 Correct 398 ms 22944 KB Output is correct
4 Correct 388 ms 22980 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5036 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5040 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 5 ms 5236 KB Output is correct
6 Correct 26 ms 6236 KB Output is correct
7 Correct 264 ms 15912 KB Output is correct
8 Correct 476 ms 23052 KB Output is correct
9 Correct 141 ms 15816 KB Output is correct
10 Correct 259 ms 15248 KB Output is correct
11 Correct 427 ms 19392 KB Output is correct
12 Correct 422 ms 19348 KB Output is correct
13 Correct 395 ms 22968 KB Output is correct