oj.uz

Submission #381833

# Submission time Handle Problem Language Result Execution time Memory
381833 2021-03-26T03:49:15 Z saarang123 Synchronization (JOI13_synchronization) C++17
100 / 100
 304 ms 24044 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxn = 100 * 1000 + 3, lgn = 19;
int tin[mxn], tout[mxn], bit[mxn], up[mxn][lgn], info[mxn], last[mxn];
bool active[mxn];
vector<int> g[mxn];
int n, m, q, tx = 1;

void upd(int x, int v) {
	for(; x <= n; x += (x & -x))
		bit[x] += v;
}

int qry(int x) {
	int res = 0;
	for(; x; x -= (x & -x))
		res += bit[x];
	return res;
}

void dfs(int v, int p = 0) {
	up[v][0] = p;
	info[v] = 1;
	tin[v] = tx++;
	for(int i = 1; i < lgn && up[v][i - 1]; i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for(int u : g[v]) if(u != p) dfs(u, v);
	tout[v] = tx;
}

int find_root(int u) {
	int lca = u, path = qry(tin[u]);
	for(int i = lgn - 1; ~i; i--)
		if(up[lca][i] && qry(tin[up[lca][i]]) == path) 
			lca = up[lca][i];
	return lca;
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    #ifdef saarang
    freopen("/home/saarang/Documents/cp/input.txt", "r", stdin);
    freopen("/home/saarang/Documents/cp/output.txt", "w", stdout);
    #endif
    cin >> n >> m >> q;
    vector<array<int, 2>> edge(n - 1);
    for(auto &[u, v] : edge) {
    	cin >> u >> v;
    	g[u].push_back(v);
    	g[v].push_back(u);
    }
    dfs(1);
    for(int i = 1; i <= n; i++) {
    	upd(tin[i], -1);
    	upd(tout[i], 1);
    }
    while(m--) {
    	int idx; cin >> idx; idx--;
    	int u = edge[idx][0], v = edge[idx][1];
    	if(up[u][0] == v)
    		swap(u, v);
    	if(active[idx]) {
    		info[v] = last[v] = info[find_root(u)];
    		upd(tin[v], -1);
    		upd(tout[v], 1);
    	} else {
    		info[find_root(u)] += info[v] - last[v];
    		upd(tin[v], 1);
    		upd(tout[v], -1);
    	}
    	active[idx] ^= 1;
    }
    while(q--){
    	int u; cin >> u;
    	cout << info[find_root(u)] << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 3 ms 2924 KB Output is correct
7 Correct 13 ms 4224 KB Output is correct
8 Correct 13 ms 4204 KB Output is correct
9 Correct 13 ms 4204 KB Output is correct
10 Correct 186 ms 18668 KB Output is correct
11 Correct 205 ms 18688 KB Output is correct
12 Correct 244 ms 23148 KB Output is correct
13 Correct 83 ms 18528 KB Output is correct
14 Correct 154 ms 17644 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 20460 KB Output is correct
2 Correct 91 ms 20204 KB Output is correct
3 Correct 110 ms 22252 KB Output is correct
4 Correct 105 ms 22252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 4 ms 2668 KB Output is correct
6 Correct 4 ms 3072 KB Output is correct
7 Correct 20 ms 4844 KB Output is correct
8 Correct 292 ms 24044 KB Output is correct
9 Correct 304 ms 23996 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 23916 KB Output is correct
2 Correct 173 ms 23256 KB Output is correct
3 Correct 166 ms 23404 KB Output is correct
4 Correct 168 ms 23532 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 4 ms 2924 KB Output is correct
6 Correct 18 ms 4332 KB Output is correct
7 Correct 228 ms 19436 KB Output is correct
8 Correct 291 ms 23916 KB Output is correct
9 Correct 107 ms 19684 KB Output is correct
10 Correct 155 ms 18924 KB Output is correct
11 Correct 123 ms 21612 KB Output is correct
12 Correct 126 ms 21612 KB Output is correct
13 Correct 164 ms 23464 KB Output is correct