oj.uz

Submission #1078414

# Submission time Handle Problem Language Result Execution time Memory
1078414 2024-08-27T16:52:45 Z nishkarsh Synchronization (JOI13_synchronization) C++14
100 / 100
 246 ms 28584 KB 
#include <bits/stdc++.h>
#define ll long long
#define vt vector
#define pb push_back
using namespace std;

int fastexp(int b, int e, int mod){
	int ans = 1;
	while(e){
		if(e&1) ans = (1ll*ans*b)%mod;
		b = (1ll*b*b)%mod;
		e >>= 1;
	}
	return ans;
}

const int N = 2e5+1;
const int mod = 998244353;
const ll INFLL = 1e18;
const int INF = 2e9;
const int logn = 20;

int fenwick[N];

void update(int ind, int val){
	while(ind < N){
		fenwick[ind] += val;
		ind += ind&(-ind);
	}
}

int query(int ind){
	int ans = 0;
	while(ind > 0){
		ans += fenwick[ind];
		ind = ind&(ind-1);
	}
	return ans;
}


int edges[N], lt[N], rt[N], par[N][logn], on[N], curr_val[N], edge_val[N];
vt<int> adj[N];
int node_cnt;

void dfs(int u, int p){
	lt[u] = ++node_cnt;
	par[u][0] = p;
	for(int v : adj[u]){
		if((u^edges[v]) == p) edges[v] = u;
		else dfs(u^edges[v], u);
	}
	rt[u] = ++node_cnt;
}

int find_ances(int u){
	for(int i = logn-1; i >= 0; i--){
		if(query(lt[par[u][i]]) == query(lt[u])) u = par[u][i];
	}
	return u;
}

void on_edge(int i){
	int u = edges[i];
	int v = par[u][0];
	int ances = find_ances(v);
	curr_val[v] = curr_val[ances];
	int new_num = curr_val[u] + curr_val[v] - edge_val[i];
	curr_val[ances] = curr_val[u] = curr_val[v] = new_num;
	update(lt[u], -1); update(rt[u], 1);
}

void off_edge(int i){
	int u = edges[i];
	int ances = find_ances(u);
	curr_val[u] = curr_val[par[u][0]] = edge_val[i] = curr_val[ances];
	update(lt[u], 1); update(rt[u], -1);
}

void solve(){
	int n,m,q,u,v;
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		edges[i] = u^v;
		adj[u].pb(i);
		adj[v].pb(i);
	}

	dfs(1,1);

	for(int j = 1; j < logn; j++) for(int i = 1; i <= n; i++) par[i][j] = par[par[i][j-1]][j-1];

	for(int i = 1; i <= n; i++){
		update(lt[i], 1), update(rt[i], -1);
		curr_val[i] = 1;
	}

	while(m--){
		cin >> u;
		on[u] ^= 1;
		if(on[u]) on_edge(u);
		else off_edge(u);
	}

	for(int i = 1; i < n; i++) if(on[i]) off_edge(i);

	while(q--){
		cin >> u;
		cout << curr_val[u] << "\n";
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t = 1;
	// cin >> t;

	while(t--) solve();

	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 3 ms 5208 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 4 ms 5212 KB Output is correct
7 Correct 15 ms 6832 KB Output is correct
8 Correct 15 ms 6744 KB Output is correct
9 Correct 14 ms 6832 KB Output is correct
10 Correct 169 ms 21588 KB Output is correct
11 Correct 168 ms 21508 KB Output is correct
12 Correct 199 ms 27728 KB Output is correct
13 Correct 92 ms 21444 KB Output is correct
14 Correct 142 ms 21072 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 24464 KB Output is correct
2 Correct 107 ms 24144 KB Output is correct
3 Correct 118 ms 27176 KB Output is correct
4 Correct 114 ms 27020 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5436 KB Output is correct
7 Correct 17 ms 7496 KB Output is correct
8 Correct 246 ms 28548 KB Output is correct
9 Correct 211 ms 28500 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 28500 KB Output is correct
2 Correct 132 ms 28240 KB Output is correct
3 Correct 128 ms 28420 KB Output is correct
4 Correct 128 ms 28244 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 15 ms 6884 KB Output is correct
7 Correct 185 ms 22356 KB Output is correct
8 Correct 214 ms 28584 KB Output is correct
9 Correct 104 ms 22476 KB Output is correct
10 Correct 143 ms 22308 KB Output is correct
11 Correct 114 ms 25680 KB Output is correct
12 Correct 126 ms 25680 KB Output is correct
13 Correct 125 ms 28416 KB Output is correct