Submission #698158

#	Time	Username	Problem	Language	Result	Execution time	Memory
698158		sysia	Synchronization (JOI13_synchronization)	C++17	100 / 100	343 ms	45748 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
template<class A, class B> auto& operator<<(ostream &o, pair<A, B> p) {
	return o << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &o, T x) -> decltype(x.end(), o) {
	o << '{'; int i = 0; for(auto e : x) o << (", ")+2*!i++ << e; return o << '}';
}
#ifdef DEBUG
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
#else
#define debug(...) {}
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e9+7, K = 20;

struct Tree{
    vector<int>tab;
    int sz;

    Tree(int n){
        sz = n;
        tab.resize(n);
    }

    void dodaj(int x, int d){
        for (;x<sz; x += (x&(-x))){
            tab[x] += d;
        }
    }

    void update(int l, int r, int v){
        dodaj(l, v);
        dodaj(r+1, -v);
    }

    int query(int where){
        int ans = 0;
        for (;where;where -= (where&(-where))) {
            ans += tab[where];
        }
        return ans;
    }
};

void solve(){
    int n, m, q; cin >> n >> m >> q;
    vector<vector<int>>g(n+1);
    vector<T>edges;
    for (int i = 1; i<n; i++){
        int a, b; cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
        edges.emplace_back(a, b);
    }
    vector<int>L(n+1), R(n+1);
    vector<int>ord = {-1}, depth(n+1);
    vector<vector<int>>up(n+1, vector<int>(K));
    function<void(int, int)>dfs = [&](int v, int pa){
        L[v] = (int)ord.size();
        ord.emplace_back(v);
        up[v][0] = pa;
        for (int i = 1; i<K; i++) up[v][i] = up[up[v][i-1]][i-1];
        for (auto x: g[v]){
            if (x == pa) continue;
            depth[x] = depth[v]+1;
            dfs(x, v);
        }
        R[v] = (int)ord.size();
        ord.emplace_back(v);
    };
    Tree fen(2*n+2);
    auto find_starego = [&](int v){
        int st = v;
        int ile = fen.query(R[v]-1);
        for (int i = K-1; i>=0; i--){
            int tmp = up[v][i];
            if (ile - fen.query(R[tmp]-1) >= depth[st] - depth[tmp]){
                v = tmp;
            }
        }
        return v;
    };
    dfs(1, 1);
    debug(L, R, ord);
    vector<T>info(n+1, {1, 0});
    vector<int>state(n+1);
    for (int i = 0; i<m; i++){
        int x; cin >> x;
        --x;
        auto [a, b] = edges[x];
        if (depth[a] < depth[b]) swap(a, b);
        if (state[x]){
            //turn off
            info[a].second = info[a].first = info[find_starego(a)].first;
            fen.update(L[a], R[a]-1, -1);
        } else {
            int what = find_starego(b);
            info[what].first -= info[a].second;
            info[what].first += info[a].first;
            fen.update(L[a], R[a]-1, +1);
        }
        state[x] ^= 1;
    }
    while (q--){
        int x; cin >> x;
        cout << info[find_starego(x)].first << "\n";
    }
}


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

    solve();

}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40