oj.uz

Submission #260194

# Submission time Handle Problem Language Result Execution time Memory
260194 2020-08-09T16:26:41 Z AMO5 Synchronization (JOI13_synchronization) C++17
100 / 100
 720 ms 20844 KB 
#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 j=1; j<=n; j++){
		cerr<<j<<" "<<bit.query(tin[j])<<" "<<lca(j)<<"\n";
	}
	// */ 
	
	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[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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 26 ms 4096 KB Output is correct
8 Correct 25 ms 4096 KB Output is correct
9 Correct 25 ms 4096 KB Output is correct
10 Correct 341 ms 15852 KB Output is correct
11 Correct 352 ms 15932 KB Output is correct
12 Correct 384 ms 20444 KB Output is correct
13 Correct 208 ms 16232 KB Output is correct
14 Correct 237 ms 15344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 17900 KB Output is correct
2 Correct 220 ms 17820 KB Output is correct
3 Correct 215 ms 20076 KB Output is correct
4 Correct 226 ms 20076 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 7 ms 2816 KB Output is correct
7 Correct 60 ms 4480 KB Output is correct
8 Correct 712 ms 20588 KB Output is correct
9 Correct 720 ms 20588 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 710 ms 20636 KB Output is correct
2 Correct 543 ms 20556 KB Output is correct
3 Correct 550 ms 20680 KB Output is correct
4 Correct 547 ms 20716 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 53 ms 4096 KB Output is correct
7 Correct 648 ms 16112 KB Output is correct
8 Correct 696 ms 20844 KB Output is correct
9 Correct 478 ms 16620 KB Output is correct
10 Correct 514 ms 16236 KB Output is correct
11 Correct 524 ms 18668 KB Output is correct
12 Correct 503 ms 18540 KB Output is correct
13 Correct 544 ms 20716 KB Output is correct