제출 #1291186

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

synchronization

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,
					 tree_order_statistics_node_update>;

#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define all(a) a.begin(),a.end()  



struct BIT{
    vector<int> bit; int sz;
    void init(int n){
        bit = vi(n+1,0); sz = n;
    }
    void add(int i, int val){
        for(; i <= sz; i+=i&-i)
            bit[i] += val;
    }
    int get(int i){
        int res = 0;
        for(; i>0; i-=i&-i)
            res += bit[i];
        return res;
    }
}bit;


const int mxn = 1e5+1, lg2 = 17;
vector<int> g[mxn];
int edge[mxn][2];
int suc[mxn][lg2], tim = 0;
int tin[mxn], tout[mxn];

int last[mxn], dp[mxn];
bool vis[mxn];


void pre_dfs(int u, int p){
    tin[u] = ++tim;
    for(int i = 1; i < lg2; i++)
        suc[u][i] = suc[suc[u][i-1]][i-1];

    for(auto v : g[u]) if(v!=p){
        suc[v][0] = u; pre_dfs(v,u);
    }

    tout[u] = tim; dp[u] = 1; vis[u] = 1;

    if(p!=u) bit.add(tin[u],1), bit.add(tout[u]+1,-1);
}

int get_root(int v){
    int u = v;
    for(int i = lg2-1; i >= 0; i--){
        if(bit.get(tin[suc[v][i]])==bit.get(tin[u])){
            v = suc[v][i];
        }
    }
    return v;
}



void solve(){
    int n,m,q; cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        int u,v; cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
        edge[i][0] = u, edge[i][1] = v;
    }
    suc[1][0] = 1; bit.init(n);
    pre_dfs(1,1);

    for(int i = 1; i < n; i++)
        if(suc[edge[i][0]][0]==edge[i][1])
            swap(edge[i][0],edge[i][1]);


    for(int t = 0; t < m; t++){
        int e; cin >> e;
        if(vis[e]){
            int u = edge[e][0], v = edge[e][1];

            int r = get_root(u);
            dp[r] = dp[v]+dp[r]-last[v];

            bit.add(tin[v],-1); bit.add(tout[v]+1,1);
            vis[e] = 0;
        }else{
            int u = edge[e][0], v = edge[e][1];

            int r = get_root(u);

            dp[v] = dp[r];
            last[v] = dp[r];

            bit.add(tin[v],1); bit.add(tout[v]+1,-1);
            vis[e] = 1;
        }
    }

    for(int i = 0; i < q; i++){
        int u; cin >> u;
        cout << dp[get_root(u)] << '\n';
    }

}



signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--){solve();}
}

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