제출 #479236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
479236		bonopo	Synchronization (JOI13_synchronization)	C++17	100 / 100	490 ms	24224 KiB

synchronization

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second

typedef long long ll;
const int MM=1e5+5, MOD=1e9+7, LOG=19;
int N, M, Q, pa[LOG][MM], bit[MM], st[MM], in[MM], ot[MM], c[MM], l[MM], dt;
pair<int,int> edg[MM];
vector<int> adj[MM];

void upd(int idx, int v) {
    for(; idx<MM; idx+=idx&-idx) bit[idx]+=v;
}

int qry(int idx) {
    int ret=0;
    for(; idx>=1; idx-=idx&-idx) ret+=bit[idx];
    return ret;
}

void dfs(int u, int fa) {
    pa[0][u]=fa; in[u]=++dt;
    for(int i=1; i<LOG; ++i) {
        pa[i][u]=pa[i-1][pa[i-1][u]]; }
    for(int &v:adj[u]) if(v!=fa) {
        dfs(v, u); }
    ot[u]=dt+1;
}

int rt(int u) {
    int ret=u;
    for(int i=LOG-1; i>=0; --i)
        if(pa[i][ret]&&qry(in[u])==qry(in[pa[i][ret]])) ret=pa[i][ret];
    return ret;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>N>>M>>Q;
    fill(c+1, c+N+1, 1);
    for(int i=1; i<N; ++i) {
        int u, v; cin>>u>>v;
        adj[u].pb(v), adj[v].pb(u);
        edg[i]={u,v};
    }

    dfs(1, 0);
    for(int i=1; i<N; ++i) {
        int u=edg[i].f, v=edg[i].s;
        if(in[u]>in[v]) swap(u, v);
        upd(in[v], -1);
        upd(ot[v],  1);
    }

    for(int i=1, x; i<=M; ++i) {
        cin>>x;

        int u=edg[x].f, v=edg[x].s;
        if(pa[0][u]==v) swap(u, v);

        if(st[x]) {
            // turn edge off
            upd(in[v], -1); upd(ot[v],  1);
            u=rt(u); c[v]=l[v]=c[u];
        } else {
            // turn edge on
            upd(in[v],  1); upd(ot[v], -1);
            u=rt(u); c[u]+=c[v]-l[v];
        }

        st[x]^=1;
    }

    for(int i=1, x; i<=Q; ++i) {
        cin>>x; x=rt(x);
        cout<<c[x]<<el;
    }
}

// MM

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