oj.uz

Submission #698158

# Submission time Handle Problem Language Result Execution time Memory
698158 2023-02-12T16:20:51 Z sysia Synchronization (JOI13_synchronization) C++17
100 / 100
 343 ms 45748 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 14 ms 4072 KB Output is correct
8 Correct 14 ms 4044 KB Output is correct
9 Correct 14 ms 4040 KB Output is correct
10 Correct 266 ms 37664 KB Output is correct
11 Correct 283 ms 37628 KB Output is correct
12 Correct 277 ms 44896 KB Output is correct
13 Correct 154 ms 37424 KB Output is correct
14 Correct 183 ms 37092 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 40980 KB Output is correct
2 Correct 110 ms 40584 KB Output is correct
3 Correct 139 ms 44316 KB Output is correct
4 Correct 150 ms 44184 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 19 ms 4804 KB Output is correct
8 Correct 339 ms 45640 KB Output is correct
9 Correct 343 ms 45712 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 45644 KB Output is correct
2 Correct 200 ms 45216 KB Output is correct
3 Correct 211 ms 45488 KB Output is correct
4 Correct 210 ms 45392 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 700 KB Output is correct
6 Correct 18 ms 4164 KB Output is correct
7 Correct 315 ms 38428 KB Output is correct
8 Correct 339 ms 45748 KB Output is correct
9 Correct 193 ms 38584 KB Output is correct
10 Correct 216 ms 38328 KB Output is correct
11 Correct 183 ms 42192 KB Output is correct
12 Correct 157 ms 42224 KB Output is correct
13 Correct 188 ms 45488 KB Output is correct