Submission #863520

#	Time	Username	Problem	Language	Result	Execution time	Memory
863520		lolismek	Synchronization (JOI13_synchronization)	C++14	0 / 100	355 ms	25684 KiB

synchronization

#include <iostream>
#include <vector>

#define pii pair <int, int>

using namespace std;

const int NMAX = 1e5;
const int LG = 17;

namespace AIB{
    int n;
    int aib[2 * NMAX + 1];

    void init(int _n){
        n = _n;
        for(int i = 0; i <= n; i++){
            aib[i] = 0;
        }
    }

    int lsb(int x){
        return x & -x;
    }

    void update(int pos, int val){
        for(int i = pos; i <= n; i += lsb(i)){
            aib[i] += val;
        }
    }

    int query(int pos){
        int ans = 0;
        for(int i = pos; i >= 1; i -= lsb(i)){
            ans += aib[i];
        }
        return ans;
    }
}

vector <int > adj[NMAX + 1];
pii edg[NMAX + 1];

int lvl[NMAX + 1];

int dfsTime = 0;

pii lin[NMAX + 1];

int dp[NMAX + 1][LG + 1];

void dfs(int node, int parent){
    lvl[node] = lvl[parent] + 1;

    lin[node].first = ++dfsTime;
    dp[node][0] = parent;

    for(int child : adj[node]){
        if(child != parent){
            dfs(child, node);
        }
    }

    lin[node].second = ++dfsTime;
}

bool status[NMAX + 1];
int old[NMAX + 1];

int sum[NMAX + 1];

int root(int node){
    for(int i = LG; i >= 0; i--){
        if((1 << i) < lvl[node] && AIB::query(node) == AIB::query(dp[node][i])){
            node = dp[node][i];
        }
    }
    return node;
}

int main(){

    int n, m, q;
    cin >> n >> m >> q;

    for(int i = 1; i <= n - 1; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edg[i] = {a, b};
    }

    dfs(1, 0);
    AIB::init(2 * n);

    for(int j = 1; j <= LG; j++){
        for(int i = 1; i <= n; i++){
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }

    sum[1] = 1;
    for(int i = 2; i <= n; i++){
        sum[i] = 1;
        AIB::update(lin[i].first, +1);
        AIB::update(lin[i].second, -1);
    }

    while(m--){
        int ind;
        cin >> ind;

        int node;
        if(lvl[edg[ind].first] > lvl[edg[ind].second]){
            node = edg[ind].first;
        }else{
            node = edg[ind].second;
        }

        if(status[ind]){
            sum[node] = old[node] = sum[root(node)];
            AIB::update(lin[node].first, +1);
            AIB::update(lin[node].second, -1);
        }else{
            AIB::update(lin[node].first, -1);
            AIB::update(lin[node].second, +1);

            sum[root(node)] += (sum[node] - old[node]);
            sum[node] = old[node] = 0;
        }

        status[ind] = !status[ind];
    }

    while(q--){
        int node;
        cin >> node;

        cout << sum[root(node)] + 1 << '\n';
    }

    return 0;
}

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