oj.uz

Submission #872771

# Submission time Handle Problem Language Result Execution time Memory
872771 2023-11-13T18:00:35 Z tvladm2009 Synchronization (JOI13_synchronization) C++17
100 / 100
 464 ms 30252 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) (x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using db = long double;  // or double, if TL is tight
using str = string;
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

struct AIB {
    int n;
    vector<int> aib;

    AIB(int N) : n(N), aib(N + 1, 0) {}

    void update(int x, int val) {
        for(int i = x; i <= n; i += i & -i)
            aib[i] += val;
    }

    int query(int x) {
        int sum = 0;
        for(int i = x; i >= 1; i -= i & -i)
            sum += aib[i];
        return sum;
    }

    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

struct tree {
    const int LOG = 20;
    vector<vector<int>> L;
    vector<vector<int>> Anc;
    vector<int> parent, level, l, r;
    AIB fen;
    int n;

    tree(int N) : n(N), L(N + 1), fen(N + 1), parent(N + 1, 0), level(N + 1, 0), l(N + 1), r(N + 1) {}

    void add_edge(int x, int y) {
        L[x].push_back(y);
        L[y].push_back(x);
    }

    void init() {
        int t = 0;
        function<void(int, int)> dfs = [&](int u, int par) {
            parent[u] = par;
            l[u] = ++t;
            level[u] = level[par] + 1;
            for(auto v : L[u]) {
                if(v != par) {
                    dfs(v, u);
                }
            }
            r[u] = t;
        };
        dfs(1, 0);
        Anc.push_back(parent);
        for(int k = 1; k < LOG; ++k) {
            Anc.push_back(vector<int>(n + 1, 0));
            for(int i = 1; i <= n; ++i)
                Anc[k][i] = Anc[k - 1][Anc[k - 1][i]];
        }
//        for(int i = 1; i < n; ++i) {
//            for(int k = 0; k <= 2; ++k)
//                cout << Anc[k][i] << " ";
//            cout << "\n";
//        }
    }

    int lift(int a, int x) {
        for(int k = 0; k < LOG; k++)
            if(x & (1 << k))
                a = Anc[k][a];
        return a;
    }

    int lca(int a, int b) {
        if(level[a] < level[b])
            swap(a, b);
        a = lift(a, level[b] - level[a]);
        for(int k = LOG - 1; k >= 0; k--) {
            if(Anc[k][a] != Anc[k][b]) {
                a = Anc[k][a];
                b = Anc[k][b];
            }
        }
        return Anc[0][a];
    }

    void upd(int u, int sgn) {
        fen.update(l[u], sgn);
        sgn *= -1;
        fen.update(r[u] + 1, sgn);
    }

    int go_up(int u) {
        for(int i = LOG - 1; i >= 0; --i) {
            int x = Anc[i][u];
            if(fen.query(l[x] + 1, l[u]) == level[u] - level[x])
                u = Anc[i][u];
        }
        return u;
    }
};

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

    int n, m, q;
    cin >> n >> m >> q;
    tree T(n);
    vector<pair<int, int>> edge;
    for(int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        edge.push_back({x, y});
        T.add_edge(x, y);
    }
    T.init();
    vector<int> cnt(n + 1, 1), cnt2(n + 1, 0);
    vector<int> active(n, 0);
    while(m--) {
        int i;
        cin >> i;
        --i;
        int x = edge[i].first, y = edge[i].second;
        if(T.level[x] > T.level[y]) swap(x, y);
        x = T.go_up(x);
        if(!active[i]) {
            cnt[x] += cnt[y] - cnt2[y];
            T.upd(y, +1);
        } else {
            T.upd(y, -1);
            cnt[y] = cnt2[y] = cnt[x];
        }
        active[i] ^= 1;
    }

    while(q--) {
        int x;
        cin >> x;
        x = T.go_up(x);
        cout << cnt[x] << "\n";
    }
    return 0;
}

Compilation message

synchronization.cpp: In constructor 'tree::tree(int)':
synchronization.cpp:47:9: warning: 'tree::n' will be initialized after [-Wreorder]
   47 |     int n;
      |         ^
synchronization.cpp:43:25: warning:   'std::vector<std::vector<int> > tree::L' [-Wreorder]
   43 |     vector<vector<int>> L;
      |                         ^
synchronization.cpp:49:5: warning:   when initialized here [-Wreorder]
   49 |     tree(int N) : n(N), L(N + 1), fen(N + 1), parent(N + 1, 0), level(N + 1, 0), l(N + 1), r(N + 1) {}
      |     ^~~~
synchronization.cpp:46:9: warning: 'tree::fen' will be initialized after [-Wreorder]
   46 |     AIB fen;
      |         ^~~
synchronization.cpp:45:17: warning:   'std::vector<int> tree::parent' [-Wreorder]
   45 |     vector<int> parent, level, l, r;
      |                 ^~~~~~
synchronization.cpp:49:5: warning:   when initialized here [-Wreorder]
   49 |     tree(int N) : n(N), L(N + 1), fen(N + 1), parent(N + 1, 0), level(N + 1, 0), l(N + 1), r(N + 1) {}
      |     ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 16 ms 2292 KB Output is correct
8 Correct 13 ms 2392 KB Output is correct
9 Correct 14 ms 2392 KB Output is correct
10 Correct 275 ms 19912 KB Output is correct
11 Correct 223 ms 19860 KB Output is correct
12 Correct 281 ms 29128 KB Output is correct
13 Correct 78 ms 19852 KB Output is correct
14 Correct 132 ms 19520 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 22600 KB Output is correct
2 Correct 83 ms 24200 KB Output is correct
3 Correct 82 ms 28616 KB Output is correct
4 Correct 84 ms 28612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 18 ms 3384 KB Output is correct
8 Correct 320 ms 30120 KB Output is correct
9 Correct 318 ms 29996 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 27072 KB Output is correct
2 Correct 130 ms 29636 KB Output is correct
3 Correct 138 ms 29872 KB Output is correct
4 Correct 131 ms 29956 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 17 ms 2648 KB Output is correct
7 Correct 260 ms 20728 KB Output is correct
8 Correct 464 ms 30252 KB Output is correct
9 Correct 108 ms 20884 KB Output is correct
10 Correct 158 ms 20588 KB Output is correct
11 Correct 113 ms 25692 KB Output is correct
12 Correct 113 ms 25540 KB Output is correct
13 Correct 134 ms 29896 KB Output is correct