Submission #872771

#	Time	Username	Problem	Language	Result	Execution time	Memory
872771		tvladm2009	Synchronization (JOI13_synchronization)	C++17	100 / 100	464 ms	30252 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40