oj.uz

Submission #240159

# Submission time Handle Problem Language Result Execution time Memory
240159 2020-06-18T09:27:24 Z MvC Synchronization (JOI13_synchronization) C++11
100 / 100
 258 ms 21240 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
using namespace std;
int n,m,q,i,t,tin[nmax],tout[nmax],up[nmax][20],rs[nmax],fw[nmax],ex[nmax],ey[nmax],x,y,z,l[nmax];
vector<int>a[nmax];
void dfs(int x,int p)
{
	tin[x]=++t;
	up[x][0]=p;
	for(int i=1;i<17;i++)up[x][i]=up[up[x][i-1]][i-1];
	for(int i=0;i<lun(a[x]);i++)if(a[x][i]!=p)dfs(a[x][i],x);
	tout[x]=t;
}
void upd(int i,int v)
{
	for(;i<=n;i+=i&(-i))fw[i]+=v;
}
int qry(int i)
{
	int ans=0;
	for(;i>=1;i-=i&(-i))ans+=fw[i];
	return ans;
}
int fnd(int x)
{
	int cur=qry(tin[x]);
	for(int i=16;i>=0;i--)if(qry(tin[up[x][i]])==cur)x=up[x][i];
	return x;
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	for(i=1;i<n;i++)
	{
		cin>>x>>y;
		ex[i]=x,ey[i]=y;
		a[x].pb(y);
		a[y].pb(x);
	}
	dfs(1,1);
	for(i=1;i<=n;i++)
	{
		upd(tin[i],1);
		upd(tout[i]+1,-1);
		rs[i]=1;
	}
	for(i=1;i<n;i++)if(tin[ex[i]]>tin[ey[i]])swap(ex[i],ey[i]);
	while(m--)
	{
		cin>>i;
		x=ex[i],y=ey[i],z=fnd(x);
		if(l[i]==-1)
		{
			upd(tin[y],1);
			upd(tout[y]+1,-1);
			l[i]=rs[y]=rs[z];
		}
		else
		{
			upd(tin[y],-1);
			upd(tout[y]+1,1);
			rs[z]+=rs[y]-l[i];
			l[i]=-1;
		}
	}
	while(q--)
	{
		cin>>x;
		cout<<rs[fnd(x)]<<'\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 8 ms 2944 KB Output is correct
7 Correct 17 ms 4224 KB Output is correct
8 Correct 16 ms 4224 KB Output is correct
9 Correct 19 ms 4352 KB Output is correct
10 Correct 247 ms 16632 KB Output is correct
11 Correct 244 ms 16760 KB Output is correct
12 Correct 213 ms 20728 KB Output is correct
13 Correct 101 ms 17008 KB Output is correct
14 Correct 126 ms 16632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 18808 KB Output is correct
2 Correct 91 ms 18680 KB Output is correct
3 Correct 106 ms 20636 KB Output is correct
4 Correct 100 ms 20600 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 7 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 22 ms 4736 KB Output is correct
8 Correct 257 ms 20984 KB Output is correct
9 Correct 258 ms 20824 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 20856 KB Output is correct
2 Correct 161 ms 21196 KB Output is correct
3 Correct 153 ms 21204 KB Output is correct
4 Correct 160 ms 21240 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 7 ms 2816 KB Output is correct
5 Correct 7 ms 2944 KB Output is correct
6 Correct 21 ms 4352 KB Output is correct
7 Correct 243 ms 17028 KB Output is correct
8 Correct 258 ms 20984 KB Output is correct
9 Correct 128 ms 17520 KB Output is correct
10 Correct 159 ms 17400 KB Output is correct
11 Correct 130 ms 19576 KB Output is correct
12 Correct 130 ms 19596 KB Output is correct
13 Correct 161 ms 21240 KB Output is correct