oj.uz

Submission #240164

# Submission time Handle Problem Language Result Execution time Memory
240164 2020-06-18T10:02:01 Z Knps4422 Synchronization (JOI13_synchronization) C++14
100 / 100
 321 ms 20984 KB 
//#pragma optimization_level 3
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordset;
*/
#define fr first
#define sc second
#define vec vector
#define pb push_back
#define pii pair<int, int>
#define forr(x,y,z) for(int x = (int)y ; x <= (int)z ; ++x)
#define forn(x,y) for(int x = 1; x <= (int)y; ++x)
#define all(x) (x).begin(),(x).end()
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pll;
typedef unsigned int uint;
typedef complex<ll> point;
const int nmax = 100005;
const ll linf = 1e18;
const ll mod = 1e9+7;
const int inf = 1e9;

int n, m , q;

vec < int > g[nmax];
int tin[nmax], tout[nmax], tt;
int bit[nmax];
pii ed[nmax];
int up[nmax][17];
int old[nmax], cur[nmax], active[nmax];
void update(int pos , int val){
	for(;pos <= n; pos += pos&-pos){
		bit[pos] += val;
	}
}
int query(int pos ){
	int rs = 0;
	for(;pos > 0 ; pos -= pos&-pos){
		rs += bit[pos];
	}
	return rs;
}

void dfs(int nod , int p){
	tin[nod] = ++tt;
	up[nod][0] = p;
	forn(i,16){
		up[nod][i] = up[up[nod][i-1]][i-1];
	}
	for(int j : g[nod]){
		if(j != p){
			dfs(j,nod);
		}
	}
	tout[nod] = tt;
	update(tin[nod],1);
	update(tout[nod]+1,-1);
}

int find_root(int nod){
	int p = nod;
	int qr = query(tin[nod]);
	for(int i = 16 ; i >= 0 ; i--){
		if(query(tin[up[p][i]]) == qr){
			p = up[p][i];
		}
	}
	return p;
}
int a, b;
int main(){
	fast
	cin >> n >> m >> q;
	forn(i,n-1){
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
		ed[i] = {a,b};
		active[i] = 0;
	}
	dfs(1,1);
	forn(i,n-1){
		if(up[ed[i].fr][0]!=ed[i].sc){
			swap(ed[i].fr,ed[i].sc);
		}
	}
	forn(i,n){
		old[i] = 0;
		cur[i] = 1;
	}


	int ei;
	forn(jj,m){
		cin >> ei;
		if(active[ei]){
			int rt = find_root(ed[ei].sc);
			cur[ed[ei].fr] = cur[rt];
			old[ed[ei].fr] = cur[rt];
			update(tin[ed[ei].fr],1);
			update(tout[ed[ei].fr]+1,-1);
		}else{
			int rt = find_root(ed[ei].sc);
			cur[rt] += cur[ed[ei].fr] - old[ed[ei].fr];
			update(tin[ed[ei].fr],-1);
			update(tout[ed[ei].fr]+1,1);
		}
		active[ei] ^= 1;
	}
	forn(i,q){
		cin >> a;
		cout << cur[find_root(a)] << '\n';
	}
}

Subtask #1
10.0 / 10.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 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 7 ms 2688 KB Output is correct
7 Correct 19 ms 3968 KB Output is correct
8 Correct 18 ms 4096 KB Output is correct
9 Correct 18 ms 3968 KB Output is correct
10 Correct 232 ms 15740 KB Output is correct
11 Correct 225 ms 15736 KB Output is correct
12 Correct 256 ms 20344 KB Output is correct
13 Correct 119 ms 15984 KB Output is correct
14 Correct 163 ms 15736 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 18168 KB Output is correct
2 Correct 118 ms 18040 KB Output is correct
3 Correct 110 ms 20216 KB Output is correct
4 Correct 115 ms 20344 KB Output is correct

Subtask #3
10.0 / 10.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 6 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 24 ms 4480 KB Output is correct
8 Correct 314 ms 20472 KB Output is correct
9 Correct 315 ms 20600 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 20472 KB Output is correct
2 Correct 177 ms 20856 KB Output is correct
3 Correct 169 ms 20984 KB Output is correct
4 Correct 175 ms 20856 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 6 ms 2688 KB Output is correct
5 Correct 8 ms 2816 KB Output is correct
6 Correct 23 ms 4096 KB Output is correct
7 Correct 269 ms 15968 KB Output is correct
8 Correct 321 ms 20608 KB Output is correct
9 Correct 154 ms 16496 KB Output is correct
10 Correct 189 ms 16376 KB Output is correct
11 Correct 156 ms 18808 KB Output is correct
12 Correct 153 ms 18808 KB Output is correct
13 Correct 181 ms 20984 KB Output is correct