oj.uz

Submission #984352

# Submission time Handle Problem Language Result Execution time Memory
984352 2024-05-16T14:21:31 Z LOLOLO Synchronization (JOI13_synchronization) C++17
100 / 100
 194 ms 26088 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 1e5 + 10;
vector <int> ed[N];
int p[N][20], f[N], in[N], ou[N], timer = 1, num[N], pr[N], used[N];

void upd(int i, int x) {
    for (; i < N; i += i & (-i))
        f[i] += x;
}

int get(int i) {
    int s = 0;
    for (; i; i -= i & (-i))
        s += f[i];

    return s;
} 

void dfs(int u, int v) {
    in[u] = timer++;
    p[u][0] = v;
    for (int j = 1; j < 20; j++)
        p[u][j] = p[p[u][j - 1]][j - 1];

    for (auto x : ed[u]) {
        if (x == v)
            continue;

        dfs(x, u);
    }

    ou[u] = timer;
    upd(in[u], 1);
    upd(ou[u], -1);
}

int root(int x) {
    int v = get(in[x]);

    for (int j = 19; j >= 0; j--) {
        if (get(in[p[x][j]]) == v)
            x = p[x][j];
    }

    return x;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m, q;
    cin >> n >> m >> q;

    vector <pair <int, int>> save;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        ed[a].pb(b);
        ed[b].pb(a);
        save.pb({a, b});
    }

    dfs(1, 1);

    for (int i = 1; i <= n; i++) {
        num[i] = 1;
    }

    for (int i = 1; i <= m; i++) {
        int id;
        cin >> id;
        id--;
        int a = save[id].f, b = save[id].s;
        if (p[a][0] == b)
            swap(a, b);

        if (used[id] == -1) {
            // remove edge
            int r = root(a);
            upd(in[b], 1);
            upd(ou[b], -1);
            num[b] = used[id] = num[r];
        } else {
            // insert edge
            int r = root(a);
            upd(in[b], -1);
            upd(ou[b], 1);
            num[r] += abs(num[b] - used[id]);
            used[id] = -1;
        } 
    }

    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        cout << num[root(x)] << '\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 3 ms 8536 KB Output is correct
7 Correct 14 ms 9172 KB Output is correct
8 Correct 11 ms 9308 KB Output is correct
9 Correct 11 ms 9308 KB Output is correct
10 Correct 122 ms 19248 KB Output is correct
11 Correct 142 ms 19140 KB Output is correct
12 Correct 148 ms 25448 KB Output is correct
13 Correct 77 ms 19128 KB Output is correct
14 Correct 91 ms 18480 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 22104 KB Output is correct
2 Correct 79 ms 21900 KB Output is correct
3 Correct 75 ms 24796 KB Output is correct
4 Correct 73 ms 24772 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8536 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 15 ms 9992 KB Output is correct
8 Correct 192 ms 26088 KB Output is correct
9 Correct 194 ms 26056 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 26088 KB Output is correct
2 Correct 116 ms 25824 KB Output is correct
3 Correct 115 ms 25896 KB Output is correct
4 Correct 117 ms 25988 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8700 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 15 ms 9308 KB Output is correct
7 Correct 163 ms 20164 KB Output is correct
8 Correct 194 ms 26048 KB Output is correct
9 Correct 103 ms 20160 KB Output is correct
10 Correct 113 ms 19936 KB Output is correct
11 Correct 112 ms 23332 KB Output is correct
12 Correct 107 ms 23268 KB Output is correct
13 Correct 116 ms 25924 KB Output is correct