Submission #1079415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079415		Hamed_Ghaffari	Synchronization (JOI13_synchronization)	C++17	100 / 100	220 ms	24400 KiB

synchronization

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

#define pb push_back

const int MXN = 1e5+5;
const int LOG = 17;

int fen[MXN];
inline void updx(int p, int x) {
    for(p+=2; p<MXN; p+=p&-p) fen[p] += x;
}
inline int getx(int p) {
    int res=0;
    for(p+=2; p; p-=p&-p) res += fen[p];
    return res;
}

int n, m, q, par[LOG][MXN], E[MXN], ans[MXN], lst[MXN];
bool on[MXN];
vector<int> g[MXN];
int stt[MXN], fnt[MXN], timer;

void dfs(int v) {
    ans[v] = 1;
    stt[v] = ++timer;
    for(int i=1; i<LOG; i++) par[i][v] = par[i-1][par[i-1][v]];
    for(int i : g[v])
        if((E[i]^v) == par[0][v]) E[i] = v;
        else par[0][E[i]^v]=v, dfs(E[i]^v);
    fnt[v] = timer+1;
    if(par[0][v]) updx(stt[v], 1), updx(fnt[v], -1);
}

int get_root(int v) {
    for(int i=LOG-1; i>=0; i--)
        if(par[i][v] && getx(stt[par[i][v]])==getx(stt[v]))
            v = par[i][v];
    return v;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i=1,u,v; i<n; i++) {
        cin >> u >> v;
        E[i] = u^v;
        g[u].pb(i);
        g[v].pb(i);
    }
    dfs(1);
    while(m--) {
        int v;
        cin >> v; v = E[v];
        if(on[v]) {
            ans[v] = lst[v] = ans[get_root(v)];
            updx(stt[v], 1); updx(fnt[v], -1);
        }
        else {
            updx(stt[v], -1); updx(fnt[v], 1);
            ans[get_root(v)] += ans[v]-lst[v];
        }
        on[v] ^= 1;
    }
    while(q--) {
        int v;
        cin >> v;
        cout << ans[get_root(v)] << '\n';
    }
    return 0;
}

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