oj.uz

Submission #73781

# Submission time Handle Problem Language Result Execution time Memory
73781 2018-08-29T03:27:15 Z zscoder Synchronization (JOI13_synchronization) C++17
100 / 100
 361 ms 68756 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2940 KB Output is correct
2 Correct 6 ms 3100 KB Output is correct
3 Correct 7 ms 3148 KB Output is correct
4 Correct 7 ms 3280 KB Output is correct
5 Correct 7 ms 3336 KB Output is correct
6 Correct 9 ms 3336 KB Output is correct
7 Correct 24 ms 4408 KB Output is correct
8 Correct 22 ms 4676 KB Output is correct
9 Correct 21 ms 4752 KB Output is correct
10 Correct 328 ms 13952 KB Output is correct
11 Correct 340 ms 16184 KB Output is correct
12 Correct 222 ms 23136 KB Output is correct
13 Correct 225 ms 23136 KB Output is correct
14 Correct 227 ms 23136 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 26512 KB Output is correct
2 Correct 147 ms 28184 KB Output is correct
3 Correct 111 ms 32184 KB Output is correct
4 Correct 104 ms 33900 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33900 KB Output is correct
2 Correct 5 ms 33900 KB Output is correct
3 Correct 5 ms 33900 KB Output is correct
4 Correct 6 ms 33900 KB Output is correct
5 Correct 5 ms 33900 KB Output is correct
6 Correct 7 ms 33900 KB Output is correct
7 Correct 21 ms 33900 KB Output is correct
8 Correct 251 ms 37628 KB Output is correct
9 Correct 341 ms 40536 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 43428 KB Output is correct
2 Correct 140 ms 45596 KB Output is correct
3 Correct 185 ms 48060 KB Output is correct
4 Correct 141 ms 50380 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 50380 KB Output is correct
2 Correct 5 ms 50380 KB Output is correct
3 Correct 6 ms 50380 KB Output is correct
4 Correct 4 ms 50380 KB Output is correct
5 Correct 6 ms 50380 KB Output is correct
6 Correct 22 ms 50380 KB Output is correct
7 Correct 361 ms 50380 KB Output is correct
8 Correct 285 ms 56512 KB Output is correct
9 Correct 244 ms 56512 KB Output is correct
10 Correct 261 ms 56652 KB Output is correct
11 Correct 164 ms 61900 KB Output is correct
12 Correct 201 ms 64272 KB Output is correct
13 Correct 131 ms 68756 KB Output is correct