oj.uz

Submission #208299

# Submission time Handle Problem Language Result Execution time Memory
208299 2020-03-10T15:48:19 Z YJU Synchronization (JOI13_synchronization) C++14
100 / 100
 417 ms 41700 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=4e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<62);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

ll n,x,y,m,q,bit[N],in[N],out[N],ti=1,lca[N][21],cd,ans[N],last[N],B[N];
vector<pll> edge;
vector<ll> v[N];

void DFS(ll nd,ll pa){
	lca[nd][0]=pa;
	in[nd]=ti++;
	ans[nd]=1;
	for(ll i=1;i<=20&&lca[nd][i-1];i++)lca[nd][i]=lca[lca[nd][i-1]][i-1];
	for(auto i:v[nd]){
		if(i==pa)continue;
		DFS(i,nd);
	}
	out[nd]=ti;
}

void mod(ll id,ll dx){
	while(id<N)bit[id]+=dx,id+=(id&-id);
}

ll query(ll id){
	ll tmp=0;while(id)tmp+=bit[id],id-=(id&-id);return tmp;
}

ll find(ll id){
	ll tmp=id;
	for(ll i=20;i>=0;i--)if(lca[tmp][i]&&query(in[lca[tmp][i]])==query(in[id]))tmp=lca[tmp][i];
	return tmp;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m>>q;
	REP(i,n-1){
		cin>>x>>y;
		edge.pb(mp(x,y));
		v[x].pb(y);v[y].pb(x);
	}
	DFS(1,0);
	REP1(i,n)mod(in[i],-1),mod(out[i],1);
	REP(i,m){
		cin>>cd;
		y=edge[cd-1].Y;x=edge[cd-1].X;
		if(lca[y][0]==x)swap(x,y);
		if(B[cd-1]){
			ans[x]=last[x]=ans[find(y)];
			mod(in[x],-1),mod(out[x],1);
		}else{
			ans[find(y)]+=ans[x]-last[x];
			mod(in[x],1),mod(out[x],-1);
		}
		B[cd-1]=1-B[cd-1];
	}
	while(q--)cin>>x,cout<<ans[find(x)]<<"\n";
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 10 ms 9720 KB Output is correct
3 Correct 10 ms 9848 KB Output is correct
4 Correct 10 ms 9848 KB Output is correct
5 Correct 10 ms 9848 KB Output is correct
6 Correct 11 ms 10104 KB Output is correct
7 Correct 27 ms 12660 KB Output is correct
8 Correct 23 ms 12644 KB Output is correct
9 Correct 23 ms 12660 KB Output is correct
10 Correct 243 ms 37476 KB Output is correct
11 Correct 259 ms 37348 KB Output is correct
12 Correct 322 ms 41444 KB Output is correct
13 Correct 139 ms 37604 KB Output is correct
14 Correct 177 ms 36716 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 38876 KB Output is correct
2 Correct 120 ms 38500 KB Output is correct
3 Correct 156 ms 40804 KB Output is correct
4 Correct 152 ms 40804 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 10 ms 9848 KB Output is correct
3 Correct 10 ms 9900 KB Output is correct
4 Correct 10 ms 9852 KB Output is correct
5 Correct 11 ms 9848 KB Output is correct
6 Correct 12 ms 10108 KB Output is correct
7 Correct 30 ms 13172 KB Output is correct
8 Correct 385 ms 41700 KB Output is correct
9 Correct 396 ms 41700 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 41700 KB Output is correct
2 Correct 227 ms 41188 KB Output is correct
3 Correct 221 ms 41448 KB Output is correct
4 Correct 231 ms 41348 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 10 ms 9848 KB Output is correct
3 Correct 10 ms 9848 KB Output is correct
4 Correct 10 ms 9852 KB Output is correct
5 Correct 11 ms 10104 KB Output is correct
6 Correct 27 ms 12660 KB Output is correct
7 Correct 300 ms 37740 KB Output is correct
8 Correct 417 ms 41672 KB Output is correct
9 Correct 162 ms 38116 KB Output is correct
10 Correct 199 ms 37348 KB Output is correct
11 Correct 160 ms 39524 KB Output is correct
12 Correct 159 ms 39528 KB Output is correct
13 Correct 226 ms 41520 KB Output is correct