oj.uz

Submission #968661

# Submission time Handle Problem Language Result Execution time Memory
968661 2024-04-23T19:53:58 Z Lecorbio Synchronization (JOI13_synchronization) C++17
100 / 100
 309 ms 26964 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define sajz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5+7, P = 20, B = 1<<17;
int n, m, q, timer = -1, dist[N], tin[N], tout[N], up[N][P], val[N], last[N], tree[B*2];
pair<int,int> edge[N];
vector<int> g[N];
bool active[N];

void dfs(int v, int par){
	tin[v] = ++timer;
	val[v] = 1;
	up[v][0] = par;
	for (int i=1; i<P; i++) up[v][i] = up[up[v][i-1]][i-1];
	for (auto u : g[v]){
		if (u == par) continue;
		dist[u] = dist[v] + 1;
		dfs(u, v);
	}
	tout[v] = timer;
}

void update(int v, int a, int b, int p, int k, int x){
	if (a > k || b < p) return;
	else if (a >= p && b <= k){
		tree[v] += x;
		return;
	}
	int mid = (a+b) / 2;
	update(v*2, a, mid, p, k, x); update(v*2+1, mid+1, b, p, k, x);
}
int query(int v){
	v += B;
	int res = 0;
	while (v){
		res += tree[v];
		v /= 2;
	}
	return res;
}

int find_root(int v){
	int x = query(tin[v]);
	for (int i=P-1; i>=0; i--){
		if (query(tin[up[v][i]]) == x) v = up[v][i];
	}
	return v;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m >> q;
    for (int i=1; i<n; i++){
		int a, b; cin >> a >> b;
		edge[i] = {a, b};
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	dist[1] = 1;
	dfs(1, 1);
	for (int i=1; i<=n; i++) tree[tin[i]+B] = -dist[i];
	
	for (int i=0; i<m; i++){
		int x; cin >> x;
		auto [a, b] = edge[x];
		if (tin[b] > tin[a]) swap(a, b);
		
		if (!active[x]){
			val[find_root(b)] += val[a] - last[a];
			update(1, 0, B-1, tin[a], tout[a], 1);
			active[x] = true;
		}else{
			val[a] = last[a] = val[find_root(b)];
			update(1, 0, B-1, tin[a], tout[a], -1);
			active[x] = false;
		}
	}
	
	for (int i=0; i<q; i++){
		int v; cin >> v;
		cout << val[find_root(v)] << '\n';
	}
	
    return 0;
}
/*

5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
1
4
5

*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 19 ms 7260 KB Output is correct
8 Correct 21 ms 7256 KB Output is correct
9 Correct 20 ms 7256 KB Output is correct
10 Correct 212 ms 20016 KB Output is correct
11 Correct 220 ms 19788 KB Output is correct
12 Correct 237 ms 26068 KB Output is correct
13 Correct 177 ms 19916 KB Output is correct
14 Correct 142 ms 19280 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 22744 KB Output is correct
2 Correct 172 ms 22604 KB Output is correct
3 Correct 110 ms 25420 KB Output is correct
4 Correct 114 ms 25428 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 27 ms 8008 KB Output is correct
8 Correct 299 ms 26804 KB Output is correct
9 Correct 296 ms 26964 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 26424 KB Output is correct
2 Correct 183 ms 26420 KB Output is correct
3 Correct 180 ms 26576 KB Output is correct
4 Correct 181 ms 26772 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 26 ms 7260 KB Output is correct
7 Correct 309 ms 20932 KB Output is correct
8 Correct 304 ms 26792 KB Output is correct
9 Correct 252 ms 20936 KB Output is correct
10 Correct 198 ms 20560 KB Output is correct
11 Correct 247 ms 24048 KB Output is correct
12 Correct 241 ms 24144 KB Output is correct
13 Correct 184 ms 26612 KB Output is correct