Submission #220761

#	Time	Username	Problem	Language	Result	Execution time	Memory
220761		tictaccat	Synchronization (JOI13_synchronization)	C++14	100 / 100	867 ms	26360 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 100;

int N,M,Q,C;
vector<vector<int>> adj(MAX);
vector<pair<int,int>> el;
vector<bool> active(MAX);

int cnt;
vector<int> p(MAX), explored(MAX), pre(MAX), post(MAX), dep(MAX);
vector<vector<int>> anc(20, vector<int>(MAX));
vector<int> a(MAX, 1), c(MAX,0);

vector<int> tr(MAX);

void dfs(int u) {
    explored[u] = true;
    pre[u] = cnt++;
    for (int v: adj[u]) {
        if (explored[v]) continue;
        p[v] = u;
        dep[v] = dep[u]+1;
        dfs(v);
    }
    post[u] = cnt-1;
   // cout << u+1 << " " << pre[u] << " " << post[u] << "\n";
}

void add(int i, int x) {
    i++;
    while (i <= N) {
        tr[i] += x;
        i += i&-i;
    }
}
int sum(int i) {
    i++;
    int s = 0;
    while (i > 0) {
        s += tr[i];
        i -= i&-i;
    }
    return s;
} 

void add_edge(int u, int v) {
    add(pre[u],v);
    add(post[u]+1,-v);
}

int num_edges(int u) {
    return sum(pre[u]);
}

bool connect(int u, int v) {
    return (num_edges(u) - num_edges(v)) == (dep[u] - dep[v]);
}

int find_root(int v) {
    int root = v;
    for (int k = 19; k >= 0; k--) {
        while (connect(anc[k][root], root) && root != C) root = anc[k][root];
    }
    return root;
}

int main() {

    cin >> N >> M >> Q;

    for (int i = 0; i < N-1; i++) {
        int X,Y;
        cin >> X >> Y;
        X--; Y--;
        adj[X].push_back(Y);
        adj[Y].push_back(X);
        el.emplace_back(X,Y);
    }

    vector<int> darr(M);
    for (int i = 0; i < M; i++) {
        cin >> darr[i];
        darr[i]--;
    }

    C = 1;
    C--;
    dfs(C);
    p[C] = C;

    for (int i = 0; i < N; i++) {
        anc[0][i] = p[i];
    }
    for (int k = 1; k < 20; k++) {
        for (int i = 0; i < N; i++) {
            anc[k][i] = anc[k-1][anc[k-1][i]];
        }
    }

    // cout << find_root(2-1)+1 << "\n";
    // add_edge(2-1, 1);
    // cout << find_root(2-1)+1 << "\n";

    // add_edge(4-1, 1);
    // add_edge(2-1,-1);
    // cout << find_root(4-1) + 1 << "\n";

    //add_edge(0,1);

    for (int d: darr) {
        active[d] = !active[d];
        int u,v;
        tie(u,v) = el[d];
        if (dep[u] < dep[v]) swap(u,v);
        int rtV = find_root(v);
        if (active[d]) {
         //   cout << "adding " << u+1 << " " << v+1 << "\n";
           // cout << num_edges(5-1) << "\n";
          //  int rtU = find_root(u);
          //  cout << rtU+1 << " " << rtV+1 << "\n";
            a[rtV] = a[rtV] + a[u] - c[u];
            //a[u] = 0;
            add_edge(u, 1);
        }
        if (!active[d]) {
            a[u] = c[u] = a[rtV];
            //cout << "removing " << u+1 << " " << v+1 << "\n";
            add_edge(u, -1);
        }
    }
    
    for (int i = 0; i < Q; i++) {
        int q;
        cin >> q;
        q--;
        cout << a[find_root(q)] << "\n";
    }

    //cout << a[C] << "\n";


    return 0;
}

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