oj.uz

Submission #381834

# Submission time Handle Problem Language Result Execution time Memory
381834 2021-03-26T03:51:06 Z saarang123 Synchronization (JOI13_synchronization) C++17
100 / 100
 302 ms 22764 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#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 2796 KB Output is correct
7 Correct 13 ms 4076 KB Output is correct
8 Correct 13 ms 4076 KB Output is correct
9 Correct 14 ms 4076 KB Output is correct
10 Correct 178 ms 16236 KB Output is correct
11 Correct 180 ms 16236 KB Output is correct
12 Correct 231 ms 22400 KB Output is correct
13 Correct 79 ms 16484 KB Output is correct
14 Correct 162 ms 15980 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 19096 KB Output is correct
2 Correct 91 ms 18924 KB Output is correct
3 Correct 108 ms 21996 KB Output is correct
4 Correct 111 ms 21996 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 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 3 ms 2668 KB Output is correct
6 Correct 4 ms 2924 KB Output is correct
7 Correct 20 ms 4716 KB Output is correct
8 Correct 301 ms 22636 KB Output is correct
9 Correct 292 ms 22636 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 22512 KB Output is correct
2 Correct 166 ms 22508 KB Output is correct
3 Correct 168 ms 22636 KB Output is correct
4 Correct 172 ms 22636 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 5 ms 2796 KB Output is correct
6 Correct 17 ms 4076 KB Output is correct
7 Correct 245 ms 16492 KB Output is correct
8 Correct 289 ms 22764 KB Output is correct
9 Correct 115 ms 16996 KB Output is correct
10 Correct 156 ms 16508 KB Output is correct
11 Correct 125 ms 19832 KB Output is correct
12 Correct 124 ms 19820 KB Output is correct
13 Correct 164 ms 22636 KB Output is correct