oj.uz

Submission #446482

# Submission time Handle Problem Language Result Execution time Memory
446482 2021-07-22T06:20:25 Z Millad Synchronization (JOI13_synchronization) C++14
100 / 100
 646 ms 26940 KB 
//In the name of god
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define debug(x) cout << #x << " : " << x << "\n"
#define use_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef string str;

const ll maxn = 2e5 + 5;
bool act[maxn];
ll n, m, q, fen[maxn], a[maxn], c[maxn], par[20][maxn], h[maxn];
ll t = 1, tin[maxn], tout[maxn];
pll p[maxn];
vector <ll> adj[maxn];
void add(int p, int x){
	for(; p; p -= (p & -p))fen[p] = (fen[p] + x);
}
int get(int p){
	int sum = 0;
	for(p ++; p < maxn; p += (p & -p))sum = (sum + fen[p]);
	return sum;
}
void dfs(ll v){
	tin[v] = t ++;
	for(ll j = 1; j < 19; j ++){
		ll u = par[j - 1][v];
		if((u == 0) || (par[j - 1][u] == 0))break;
		par[j][v] = par[j - 1][u];
	}
	for(ll j : adj[v]){
		if(j == par[0][v])continue;
		h[j] = h[v] + 1;
		par[0][j] = v;
		dfs(j);
	}
	tout[v] = t;
}
ll get_root(ll v){
	for(ll i = 18; i >= 0; i --){
		if(par[i][v] == 0)continue;
		if(get(tin[par[i][v]]) != get(tin[v]))continue;
		v = par[i][v];
	}
	return v;
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for(ll i = 1; i < n; i ++){
		cin >> p[i].F >> p[i].S;
		adj[p[i].F].pb(p[i].S);
		adj[p[i].S].pb(p[i].F);
	}
	dfs(1);
	for(ll i = 1; i <= n; i ++){
		add(tin[i], -1);
		add(tout[i], 1);
		a[i] = 1;
	}
	for(ll i = 1; i < n; i ++){
		if(h[p[i].F] > h[p[i].S]){
			swap(p[i].F, p[i].S);
		}
	}
	while(m --){
		ll ind; cin >> ind;
		ll root = get_root(p[ind].F);
		if(act[ind]){
			a[p[ind].S] = a[root];
			c[p[ind].S] = a[root];
			add(tin[p[ind].S], -1);
			add(tout[p[ind].S], 1);
		}
		else{
			a[root] += a[p[ind].S] - c[p[ind].S];
			add(tin[p[ind].S], 1);
                        add(tout[p[ind].S], -1);
		}
		act[ind] = 1 - act[ind];
	}
	while(q --){
		ll v; cin >> v;
		v = get_root(v);
		cout << a[v] << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 5 ms 5196 KB Output is correct
7 Correct 17 ms 6132 KB Output is correct
8 Correct 17 ms 6052 KB Output is correct
9 Correct 17 ms 6128 KB Output is correct
10 Correct 246 ms 15876 KB Output is correct
11 Correct 253 ms 15824 KB Output is correct
12 Correct 511 ms 26164 KB Output is correct
13 Correct 74 ms 14136 KB Output is correct
14 Correct 152 ms 15260 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 21052 KB Output is correct
2 Correct 128 ms 21060 KB Output is correct
3 Correct 152 ms 25224 KB Output is correct
4 Correct 155 ms 25168 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5016 KB Output is correct
4 Correct 4 ms 5016 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 6 ms 5196 KB Output is correct
7 Correct 35 ms 7108 KB Output is correct
8 Correct 646 ms 26940 KB Output is correct
9 Correct 641 ms 26936 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 26912 KB Output is correct
2 Correct 242 ms 26392 KB Output is correct
3 Correct 251 ms 26404 KB Output is correct
4 Correct 240 ms 26528 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5112 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 23 ms 6204 KB Output is correct
7 Correct 287 ms 16716 KB Output is correct
8 Correct 620 ms 26928 KB Output is correct
9 Correct 108 ms 15160 KB Output is correct
10 Correct 183 ms 16052 KB Output is correct
11 Correct 184 ms 22340 KB Output is correct
12 Correct 189 ms 22304 KB Output is correct
13 Correct 245 ms 26352 KB Output is correct