제출 #1304236

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

synchronization

#include <bits/stdc++.h>
using namespace std;

vector<int> tree;
int n,m,q;

vector<int> ans;
vector<int> lst;

int query(int a, int b){
    int ans = 0;
    a += n;
    b += n;
    while (a <= b){
        if (a % 2 == 1){
            ans = max(ans,tree[a]);
            a++;
        }
        if (b%2 == 0){
            ans = max(ans,tree[b]);
            b--;
        }
        a /= 2;
        b /= 2;
    }
    return ans;
}
 
void update(int k, int x){
    //pos k -> x
    k += n;
    tree[k] = x;
    k /= 2;
    while (k >= 1){
        tree[k] = max(tree[2*k], tree[2*k+1]);
        k /= 2;
    }
}

struct HLD{
    int n,timer;
    vector<vector<int>> adj;
    vector<int> parent, depth, heavy, head, pos, endd, sz;
    vector<int> rev_pos;
    
    HLD(int _n) : n(_n), timer(0), adj(_n), parent(_n,-1), depth(_n), heavy(_n,-1), head(_n), pos(_n), endd(_n), sz(_n), rev_pos(_n) {};
    
    void addedge(int u, int v){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int dfs_sz(int v){
        sz[v] = 1;
        heavy[v] = -1;
        for (int c : adj[v]){
            if (c == parent[v]) continue;
            parent[c] = v;
            depth[c] = depth[v] + 1;
            dfs_sz(c);
            sz[v] += sz[c];
            
            if (heavy[v] < 0 || sz[c] > sz[heavy[v]]){
                heavy[v] = c;
            }
        }
        return sz[v];
    }
    int decompose(int v, int h){
        head[v] = h;
        pos[v] = timer++;
        rev_pos[pos[v]] = v;
        endd[v] = pos[v];
        if (heavy[v] != -1){
            endd[v] = decompose(heavy[v], h);
        }
        for (int c : adj[v]){
            if (c == parent[v] || c == heavy[v]) continue;
            endd[v] = decompose(c, c);
        }
        return endd[v];
    }
    
    
    void init(int root = 0){
        timer = 0;
        parent[root] = -1;
        depth[root] = 0;
        dfs_sz(root);
        decompose(root,root);
    }

    void updatepoint(int v, int x){
        update(pos[v],x);
    }
    
    int get_root(int u){
        int curr = u;
        while (curr != -1){
            int top = head[curr];
            if (query(pos[top], pos[curr]) == 1){
                int lo = pos[top];
                int hi = pos[curr];
                int bst = lo;
                while (lo <= hi){
                    int mid = (lo+hi)/2;
                    if (query(mid, hi) == 1){
                        bst = mid;
                        lo = mid+1;
                    }
                    else{
                        hi = mid-1;
                    }
                }
                return rev_pos[bst];
            }
            curr = parent[top];
        }
        return 0;
    }
};

int main(){
    cin >> n >> m >> q;
    
    vector<pair<int,int>> edges;
    HLD hld(n);
    
    for (int i = 0; i<n-1; i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        hld.addedge(a,b);
        edges.push_back({a,b});
    }
    
    hld.init();
    tree.resize(2*n,0);
    
    for (int i = 1; i<n; i++){
        hld.updatepoint(i,1);
    }
    ans.assign(n,1);
    lst.resize(n);
    
    while (m--){
        int d;
        cin >> d;
        d--;
        
        auto [a,b] = edges[d];
        if (hld.depth[a] > hld.depth[b]) swap(a,b); //parent is a, b is child
        
        int flg = query(hld.pos[b], hld.pos[b]);
        if (flg){
            //theres a break somewhere, joining back
            int rtp = hld.get_root(a);
            ans[rtp] += (ans[b] - lst[b]);
            hld.updatepoint(b,0);
        }
        else{
            //theres a breakup
            int rtp = hld.get_root(b);
            ans[b] = ans[rtp];
            lst[b] = ans[rtp];
            
            hld.updatepoint(b,1);
        }
    }
    while (q--){
        int c;
        cin >> c;
        c--;
        cout << ans[hld.get_root(c)] << '\n';
    }
}

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