oj.uz

Submission #884421

# Submission time Handle Problem Language Result Execution time Memory
884421 2023-12-07T10:18:45 Z chanhchuong123 Synchronization (JOI13_synchronization) C++14
100 / 100
 245 ms 24748 KB 
#include <bits/stdc++.h>
using namespace std;
#define task ""
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const int MAX = 100010;
int n, m, q;
int timer;
int tin[MAX];
int bit[MAX];
int tout[MAX];
bool active[MAX];
int anc[17][MAX];
int a[MAX], c[MAX];
vector<int> adj[MAX];
pair<int, int> edges[MAX];

void update(int id, int delta) {
    for (; id <= n; id += id & -id)
        bit[id] += delta;
}

int get(int id) {
    int res = 0;
    for (; id > 0; id -= id & -id)
        res += bit[id];
    return  res;
}

void dfs(int u, int p) {
    if (p != -1) {
        for (int j = 1; j <= 16; ++j) anc[j][u] = anc[j - 1][anc[j - 1][u]];
    }
    tin[u] = ++timer;
    for (int v: adj[u]) if (v != p) {
        anc[0][v] = u;
        dfs(v, u);
    }
    tout[u] =  timer;
}

int root(int u) {
    int v = u;
    for (int j = 16; j >= 0; --j) if (anc[j][v] > 0) {
        if (get(tin[u]) == get(tin[anc[j][v]]))
            v = anc[j][v];
    }
    return v;
}

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

	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r",  stdin);
		freopen(task".out", "w", stdout);
	}

    cin >> n >> m >> q;
    for (int i = 1; i <= n - 1; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges[i] = {u, v};
    }
    dfs(1, -1);
    for (int i = 1; i <= n; ++i) {
        a[i] = 1;
        update(tin[i], +1);
        update(tout[i] + 1, -1);
    }

    while (m--) {
        int j; cin >> j;
        int u, v; tie(u, v) = edges[j];
        if (anc[0][u] == v) swap(u, v);

        if (active[v]) {
            a[v] = c[v] = a[root(u)];
            update(tin[v], +1);
            update(tout[v] + 1, -1);
        } else {
            a[root(u)] += a[v] - c[v];
            update(tin[v], -1);
            update(tout[v] + 1, +1);
        }

        active[v] ^= 1;
    }

    while (q--) {
        int u; cin >> u;
        cout << a[root(u)] << '\n';
    }

	return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:56:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   freopen(task".inp", "r",  stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:57:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10708 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10808 KB Output is correct
7 Correct 10 ms 11356 KB Output is correct
8 Correct 12 ms 11468 KB Output is correct
9 Correct 9 ms 11356 KB Output is correct
10 Correct 98 ms 17748 KB Output is correct
11 Correct 98 ms 17804 KB Output is correct
12 Correct 171 ms 23944 KB Output is correct
13 Correct 48 ms 17604 KB Output is correct
14 Correct 67 ms 17236 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 20712 KB Output is correct
2 Correct 55 ms 20652 KB Output is correct
3 Correct 76 ms 23288 KB Output is correct
4 Correct 73 ms 23376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 3 ms 10728 KB Output is correct
7 Correct 15 ms 12120 KB Output is correct
8 Correct 216 ms 24644 KB Output is correct
9 Correct 245 ms 24748 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 24660 KB Output is correct
2 Correct 124 ms 24452 KB Output is correct
3 Correct 125 ms 24432 KB Output is correct
4 Correct 117 ms 24400 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 12 ms 11356 KB Output is correct
7 Correct 143 ms 18448 KB Output is correct
8 Correct 232 ms 24660 KB Output is correct
9 Correct 63 ms 18656 KB Output is correct
10 Correct 91 ms 18376 KB Output is correct
11 Correct 77 ms 21936 KB Output is correct
12 Correct 78 ms 21844 KB Output is correct
13 Correct 120 ms 24404 KB Output is correct