oj.uz

Submission #260192

# Submission time Handle Problem Language Result Execution time Memory
260192 2020-08-09T16:15:34 Z AMO5 Synchronization (JOI13_synchronization) C++17
100 / 100
 772 ms 23788 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 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.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 3 ms 2688 KB Output is correct
4 Correct 2 ms 2720 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 4 ms 2896 KB Output is correct
7 Correct 28 ms 4224 KB Output is correct
8 Correct 27 ms 4224 KB Output is correct
9 Correct 28 ms 4224 KB Output is correct
10 Correct 379 ms 18104 KB Output is correct
11 Correct 369 ms 18156 KB Output is correct
12 Correct 547 ms 22900 KB Output is correct
13 Correct 242 ms 18060 KB Output is correct
14 Correct 280 ms 17260 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 20076 KB Output is correct
2 Correct 261 ms 19820 KB Output is correct
3 Correct 267 ms 21836 KB Output is correct
4 Correct 264 ms 21740 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 3 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 62 ms 4856 KB Output is correct
8 Correct 772 ms 23708 KB Output is correct
9 Correct 751 ms 23508 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 23788 KB Output is correct
2 Correct 585 ms 22868 KB Output is correct
3 Correct 595 ms 23020 KB Output is correct
4 Correct 594 ms 23024 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 3 ms 2816 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 59 ms 4348 KB Output is correct
7 Correct 682 ms 19052 KB Output is correct
8 Correct 753 ms 23532 KB Output is correct
9 Correct 511 ms 19308 KB Output is correct
10 Correct 572 ms 18496 KB Output is correct
11 Correct 549 ms 21228 KB Output is correct
12 Correct 565 ms 21312 KB Output is correct
13 Correct 608 ms 22912 KB Output is correct