제출 #1285372

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285372		Icelast	동기화 (JOI13_synchronization)	C++20	100 / 100	746 ms	25352 KiB

synchronization

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
template <class T>
struct FenwickH {
    int n;
    vector<T> bit1, bit2;
    FenwickH(){}
    void init(int x){
        n = x;
        bit1.resize(n+1, 0);
        bit2.resize(n+1, 0);
    }
    void add(int l, int r, T delta){
        for(int i = l; i <= n; i += i & -i) {
            bit1[i] += delta;
        }
        for(int i = l; i <= n; i += i & -i) {
            bit2[i] -= delta * l;
        }
        for(int i = r+1; i <= n; i+=i&-i){
            bit1[i] -= delta;
        }
        for(int i = r+1; i <= n; i+=i&-i){
            bit2[i] -= -delta*(r+1);
        }
    }
    T sum(int l, int r){
        T res = 0;
        for(int i = r; i > 0; i-=i&-i){
            res += bit1[i] * (r+1);
        }
        for(int i = r; i > 0; i-=i&-i){
            res += bit2[i];
        }
        for(int i = l-1; i > 0; i-=i&-i){
            res -= bit1[i] * l;
        }
        for(int i = l-1; i > 0; i-=i&-i){
            res -= bit2[i];
        }
        return res;
    }
};
struct Tree{
    int n, root;
    vector<int> depth, head, sz, pa;
    vector<int> f;
    Tree(int n, int root, vector<vector<int>> &adj): n(n), root(root){
        depth.resize(n+1, -1);
        head.resize(n+1);
        sz.resize(n+1, 0);
        pa.resize(n+1, -1);
        auto rootTree = [&](auto rootTree, int u, int p) -> void{
            depth[u] = depth[p]+1;
            pa[u] = p;
            sz[u] = 1;
            for(int v : adj[u]){
                if(v == p) continue;
                rootTree(rootTree, v, u);
                sz[u] += sz[v];
            }
        };
        rootTree(rootTree, root, 0);
        auto decompose = [&](auto decompose, int u, int h) -> void{
            head[u] = h;
            int heavy = -1;
            for(int v : adj[u]){
                if(v == pa[u]) continue;
                if(heavy == -1 || sz[heavy] < sz[v]) heavy = v;
            }
            if(heavy != -1) decompose(decompose, heavy, h);
            for(int v : adj[u]){
                if(v == pa[u] || v == heavy) continue;
                decompose(decompose, v, v);
            }
        };
        decompose(decompose, root, root);
        f = [&]{
            vector<array<int, 2>> first(n+1);
            vector<array<int, 2>> second(n+1);
            function<void(int, int)> dfs0 = [&](int u, int p) {
                first[u] = second[u] = {0, -1};
                for (int v : adj[u]) {
                    if (v == p) {
                        continue;
                    }
                    dfs0(v, u);
                    auto fetch = first[v];
                    fetch[0] += 1;
                    fetch[1] = v;
                    if (fetch > first[u]) {
                        swap(fetch, first[u]);
                    }
                    if (fetch > second[u]) {
                        swap(fetch, second[u]);
                    }
                }
            };
            dfs0(1, 0);

            function<void(int, int)> dfs = [&](int u, int p) {
                for (int v : adj[u]) {
                    if (v == p) {
                        continue;
                    }
                    auto fetch = first[u][1] == v ? second[u] : first[u];
                    fetch[0] += 1;
                    fetch[1] = u;
                    if (fetch > first[v]) {
                        swap(fetch, first[v]);
                    }
                    if (fetch > second[v]) {
                        swap(fetch, second[v]);
                    }
                    dfs(v, u);
                }
            };
            dfs(1, 0);
            vector<int> f(n+1);
            for (int u = 1; u <= n; u++) {
                f[u] = first[u][0];
            }
            return f;
        }();
    };
    int lca(int u, int v){
        for(; head[u] != head[v]; v = pa[head[v]]){
            if(depth[head[u]] > depth[head[v]]) swap(u, v);
        }
        if(depth[u] > depth[v]) swap(u, v);
        return u;
    }
    int dist(int u, int v) {
        return depth[u]+depth[v]-2*depth[lca(u, v)];
    }
};
struct edge{
    int u, v;
};
void solve(){
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> f(n+1, 0), g(n+1, 0);
    for(int i = 1; i <= n; i++){
        f[i]++;
    }
    vector<vector<int>> adj(n+1);
    vector<edge> e(1);
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        e.push_back({u, v});
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> lt(n+1), rt(n+1);
    int timer = 0;
    vector<int> pa(n+1);
    vector<int> depth(n+1, 0);
    auto dfs = [&](auto dfs, int u, int p) -> void{
        timer ++;
        pa[u] = p;
        lt[u] = timer;
        for(int v : adj[u]){
            if(v == p) continue;
            depth[v] = depth[u] + 1;
            dfs(dfs, v, u);
        }
        rt[u] = timer;
    };
    dfs(dfs, 1, 0);
    FenwickH<int> bit;
    bit.init(n+1);
    for(int i = 2; i <= n; i++){
        bit.add(lt[i], rt[i], 1);
    }
    int B = 19;
    vector<vector<int>> up(B+1, vector<int>(n+1, 0));
    for(int i = 1; i <= n; i++){
        up[0][i] = pa[i];
    }
    for(int j = 1; j <= B; j++){
        for(int i = 1; i <= n; i++){
            up[j][i] = up[j-1][up[j-1][i]];
        }
    }
    auto head = [&](int v) -> int{
        int u = v;
        for(int j = B; j >= 0; j--){
            int nxt = up[j][v];
            if(nxt != 0 && bit.sum(lt[u], lt[u]) - bit.sum(lt[nxt], lt[nxt]) == 0){
                v = nxt;
            }
        }
        return v;
    };
    vector<int> state(n+1, 0);
    for(int i = 1; i <= m; i++){
        int id;
        cin >> id;
        int u = e[id].u, v = e[id].v;
        if(depth[u] > depth[v]){
            swap(u, v);
        }
        int h = head(u);
        if(state[id] == 0){
            f[h] = f[h] + f[v] - g[v];
            bit.add(lt[v], rt[v], -1);
        }else{
            f[v] = f[h];
            g[v] = f[h];
            bit.add(lt[v], rt[v], 1);
        }
        state[id] ^= 1;
    }
    for(int i = 1; i <= q; i++){
        int id;
        cin >> id;
        int h = head(id);
        cout << f[h] << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("SYNCHRO.inp", "r", stdin);
    //freopen("SYNCHRO.out", "w", stdout);
    solve();
}

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