oj.uz

Submission #680725

# Submission time Handle Problem Language Result Execution time Memory
680725 2023-01-11T16:22:25 Z stevancv Synchronization (JOI13_synchronization) C++14
100 / 100
 290 ms 23536 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define sadd(a, b) a = Add(a, b)
#define smul(a, b) a = Mul(a, b)
using namespace std;
const int N = 1e5 + 2;
vector<int> g[N];
int in[N], out[N], par[N][17], tsz;
int u[N], v[N], ans[N], sync[N];
bool active[N];
void Dfs(int s, int e) {
    in[s] = ++tsz;
    par[s][0] = e;
    for (int i = 1; i < 17; i++) par[s][i] = par[par[s][i - 1]][i - 1];
    for (auto u : g[s]) {
        if (u == e) continue;
        Dfs(u, s);
    }
    out[s] = ++tsz;
}
int bit[2 * N];
void Add(int x, int v) {
    for (; x < 2 * N; x += x & (-x)) bit[x] += v;
}
int Get(int x) {
    int ans = 0;
    for (; x > 0; x -= x & (-x)) ans += bit[x];
    return ans;
}
int Getroot(int x) {
    for (int i = 16; i >= 0; i--) {
        if (par[x][i] && Get(in[par[x][i]]) == Get(in[x])) x = par[x][i];
    }
    return x;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        cin >> u[i] >> v[i];
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    Dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        ans[i] = 1;
        Add(in[i], 1);
        Add(out[i], -1);
    }
    for (int i = 1; i < n; i++) if (in[u[i]] > in[v[i]]) swap(u[i], v[i]);
    while (m--) {
        int i; cin >> i;
        if (active[i] == 0) {
            ans[Getroot(u[i])] += ans[v[i]] - sync[v[i]];
            Add(in[v[i]], -1); Add(out[v[i]], 1);
        }
        else {
            ans[v[i]] = sync[v[i]] = ans[Getroot(u[i])];
            Add(in[v[i]], 1); Add(out[v[i]], -1);
        }
        active[i] = 1 - active[i];
    }
    while (q--) {
        int x; cin >> x;
        cout << ans[Getroot(x)] << en;
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 11 ms 4180 KB Output is correct
8 Correct 11 ms 4180 KB Output is correct
9 Correct 11 ms 4180 KB Output is correct
10 Correct 188 ms 18176 KB Output is correct
11 Correct 176 ms 17960 KB Output is correct
12 Correct 218 ms 22616 KB Output is correct
13 Correct 67 ms 17976 KB Output is correct
14 Correct 113 ms 17232 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 20036 KB Output is correct
2 Correct 71 ms 19844 KB Output is correct
3 Correct 94 ms 21744 KB Output is correct
4 Correct 95 ms 21688 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2900 KB Output is correct
7 Correct 19 ms 4864 KB Output is correct
8 Correct 255 ms 23420 KB Output is correct
9 Correct 275 ms 23416 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 23536 KB Output is correct
2 Correct 157 ms 22816 KB Output is correct
3 Correct 144 ms 22860 KB Output is correct
4 Correct 153 ms 22924 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2672 KB Output is correct
5 Correct 3 ms 2900 KB Output is correct
6 Correct 15 ms 4308 KB Output is correct
7 Correct 188 ms 18892 KB Output is correct
8 Correct 290 ms 23460 KB Output is correct
9 Correct 86 ms 19076 KB Output is correct
10 Correct 134 ms 18424 KB Output is correct
11 Correct 108 ms 21156 KB Output is correct
12 Correct 103 ms 21248 KB Output is correct
13 Correct 146 ms 22876 KB Output is correct