Submission #260192

#	Time	Username	Problem	Language	Result	Execution time	Memory
260192		AMO5	Synchronization (JOI13_synchronization)	C++17	100 / 100	772 ms	23788 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()  
#define sz(x) int(x.size()) 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=63;
const int mxn=1e5+5;
bool DEBUG=0;

vector<ii>edge;
vi adj[mxn];
bool vis[mxn];	
int cnt[mxn],par[mxn][18],tin[mxn],tout[mxn],tim=1;
int lst[mxn];

struct BIT{
	vi bit;
	int N;
	void init(int n){
		N=n;
		bit.assign(n+1,0);
	}
	void add(int pos, int x){
		while(pos<=N){
			bit[pos]+=x;
			pos+=pos&-pos;
		}
	}
	int query(int pos){
		int res=0;
		while(pos){
			res+=bit[pos];
			pos-=pos&-pos;
		}
		return res;
	}
}bit;

int lca(int u){
	for(int i=17; i>=0; i--){
		if(par[u][i]&&bit.query(tin[par[u][i]])==bit.query(tin[u]))u=par[u][i];
	}
	return u;
}

void dfs(int u, int p=0){
	par[u][0]=p;
	cnt[u]=1;
	tin[u]=tim++;
	for(int v:adj[u]){
		if(v==p)continue;
		dfs(v,u);
	}
	tout[u]=tim;
}

int main()
{
    //ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    int n,m,q;
    cin>>n>>m>>q;
    bit.init(n);
    for(int i=0; i<n-1; i++){
		int u,v;
		cin>>u>>v;
		edge.eb(u,v);
		adj[u].eb(v);
		adj[v].eb(u);
	}
	dfs(1);
	for(int j=1; j<18; j++){
		for(int i=1; i<=n; i++){
			if(par[i][j-1]){
				par[i][j]=par[par[i][j-1]][j-1];
			}
		}
	}
	/*
	for(int j=1; j<=n; j++){
		cerr<<j<<" "<<bit.query(tin[j])<<" "<<lca(j)<<"\n";
	}
	// */ 
	for(int i=1; i<=n; i++){
		bit.add(tin[i],1);
		bit.add(tout[i],-1);
	}
	for(int i=0; i<m; i++){
		int ind;
		cin>>ind;
		ind--;
		vis[ind]^=1;
		int u=edge[ind].fi, v=edge[ind].se;
		if(par[u][0]==v)swap(u,v);
		//u is par of v
		if(vis[ind]){
			cnt[lca(u)]+=cnt[lca(v)]-lst[v];
			bit.add(tin[v],-1);
			bit.add(tout[v],1);
		}else{
			cnt[v]=lst[v]=cnt[lca(u)];
			bit.add(tin[v],1);
			bit.add(tout[v],-1);
		}
		/*
		cerr<<u<<"-"<<v<<" "<<vis[ind]<<"\n";
		for(int j=1; j<=n; j++){
			cerr<<j<<" "<<bit.query(tin[j])<<" "<<lca(j)<<" "<<cnt[j]<<"\n";
		}
		*/ 
	}
	for(int i=0; i<q; i++){
		int u;
		cin>>u;
		cout<<cnt[lca(u)]<<"\n";
	}
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

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