oj.uz

Submission #306346

# Submission time Handle Problem Language Result Execution time Memory
306346 2020-09-25T09:18:22 Z syy Synchronization (JOI13_synchronization) C++17
100 / 100
 313 ms 30240 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(int i = (int)a; i <= (int)b; i++)
#define DEC(i, a, b) for(int i = (int)a; i >= (int)b; i--)
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
#define f first
#define s second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<pii> vpii;
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define INF (int) 1e9 + 100
#define LLINF (ll) 1e18
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int n, m, q, a, b, p[100005], heavy[100005], head[100005], pos[100005], depth[100005];
int sz[100005], inter[100005], id[100005];
set<int> broken[100005];
vi adj[100005];
vpi edges;
bool state[100005];

int dfs(int x, int par) {
    p[x] = par;
    int sz = 1; //Total size
    int maxchild = 0; //Biggest child
    for (auto it:adj[x]) {
        if (it == par) continue;
        depth[it] = depth[x] + 1;
        int childsize = dfs(it, x); //size at child
        sz += childsize;
        if (childsize > maxchild) {
            maxchild = childsize;
            heavy[x] = it;
            // Stores the heavy child of node x
        }
    }
    return sz;
}

int coun = 1;
void decompose(int x, int h) {
    //coun is the global counter that stores the indices
    head[x] = h;
    pos[x] = coun++;
    id[pos[x]] = x;
    broken[h].insert(pos[x]);
    if (heavy[x] != -1) decompose(heavy[x], h);
    for (auto it:adj[x]) {
        if (it == p[x]) continue;
        if (it == heavy[x]) continue;
        decompose(it, it);
    }
}

int leader(int x) {
    while (broken[head[x]].empty() or *broken[head[x]].begin() > pos[x]) x = p[head[x]];
	auto it = broken[head[x]].upper_bound(pos[x]);
	return id[*(--it)];
}

int main() {
	fastio; cin >> n >> m >> q;
	edges.pb(pi(0, 0));
	FOR(i, 1, n-1) {
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
		edges.pb(pi(a, b));
	}
	memset(heavy, -1, sizeof heavy);
	dfs(1, -1); decompose(1, 1);
	FOR(i, 1, n) sz[i] = 1;
	while (m--) {
		int t; cin >> t;
		a = edges[t].f, b = edges[t].s;
		if (depth[a] < depth[b]) swap(a, b);
		if (state[t]) { //removing edge
			sz[a] = sz[leader(b)];
			inter[a] = sz[a];
			broken[head[a]].insert(pos[a]);
		} else { //adding edge
			int bl = leader(b);
			sz[bl] += sz[a] - inter[a];
			sz[a] = sz[bl];
			broken[head[a]].erase(pos[a]);
		}
		state[t] = !state[t];
	}
	while (q--) {
		cin >> a;
		cout << sz[leader(a)] << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7808 KB Output is correct
2 Correct 5 ms 7808 KB Output is correct
3 Correct 5 ms 7808 KB Output is correct
4 Correct 6 ms 7808 KB Output is correct
5 Correct 5 ms 7808 KB Output is correct
6 Correct 6 ms 7936 KB Output is correct
7 Correct 17 ms 9216 KB Output is correct
8 Correct 16 ms 9216 KB Output is correct
9 Correct 16 ms 9216 KB Output is correct
10 Correct 248 ms 21676 KB Output is correct
11 Correct 232 ms 21612 KB Output is correct
12 Correct 275 ms 29424 KB Output is correct
13 Correct 130 ms 21608 KB Output is correct
14 Correct 155 ms 20716 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 25064 KB Output is correct
2 Correct 86 ms 24940 KB Output is correct
3 Correct 102 ms 28400 KB Output is correct
4 Correct 95 ms 28392 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7808 KB Output is correct
2 Correct 5 ms 7808 KB Output is correct
3 Correct 5 ms 7808 KB Output is correct
4 Correct 6 ms 7808 KB Output is correct
5 Correct 6 ms 7808 KB Output is correct
6 Correct 7 ms 8064 KB Output is correct
7 Correct 22 ms 9984 KB Output is correct
8 Correct 307 ms 30184 KB Output is correct
9 Correct 304 ms 30240 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 30188 KB Output is correct
2 Correct 118 ms 29672 KB Output is correct
3 Correct 118 ms 29676 KB Output is correct
4 Correct 119 ms 29672 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7808 KB Output is correct
2 Correct 5 ms 7808 KB Output is correct
3 Correct 5 ms 7808 KB Output is correct
4 Correct 5 ms 7808 KB Output is correct
5 Correct 7 ms 7936 KB Output is correct
6 Correct 19 ms 9216 KB Output is correct
7 Correct 273 ms 22504 KB Output is correct
8 Correct 303 ms 30188 KB Output is correct
9 Correct 150 ms 22640 KB Output is correct
10 Correct 194 ms 21996 KB Output is correct
11 Correct 106 ms 26216 KB Output is correct
12 Correct 103 ms 26220 KB Output is correct
13 Correct 118 ms 29672 KB Output is correct