oj.uz

Submission #220761

# Submission time Handle Problem Language Result Execution time Memory
220761 2020-04-08T17:57:23 Z tictaccat Synchronization (JOI13_synchronization) C++14
100 / 100
 867 ms 26360 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13688 KB Output is correct
2 Correct 13 ms 13736 KB Output is correct
3 Correct 13 ms 13688 KB Output is correct
4 Correct 12 ms 13688 KB Output is correct
5 Correct 12 ms 13688 KB Output is correct
6 Correct 14 ms 13688 KB Output is correct
7 Correct 42 ms 14200 KB Output is correct
8 Correct 39 ms 14200 KB Output is correct
9 Correct 40 ms 14328 KB Output is correct
10 Correct 460 ms 18548 KB Output is correct
11 Correct 472 ms 18668 KB Output is correct
12 Correct 573 ms 23024 KB Output is correct
13 Correct 217 ms 18924 KB Output is correct
14 Correct 295 ms 18160 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 20972 KB Output is correct
2 Correct 208 ms 20844 KB Output is correct
3 Correct 229 ms 22636 KB Output is correct
4 Correct 225 ms 22640 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13688 KB Output is correct
2 Correct 12 ms 13688 KB Output is correct
3 Correct 13 ms 13688 KB Output is correct
4 Correct 13 ms 13688 KB Output is correct
5 Correct 13 ms 13688 KB Output is correct
6 Correct 17 ms 13816 KB Output is correct
7 Correct 66 ms 14960 KB Output is correct
8 Correct 839 ms 26220 KB Output is correct
9 Correct 867 ms 26360 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 815 ms 23336 KB Output is correct
2 Correct 555 ms 25580 KB Output is correct
3 Correct 554 ms 25708 KB Output is correct
4 Correct 557 ms 25580 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13688 KB Output is correct
2 Correct 12 ms 13688 KB Output is correct
3 Correct 12 ms 13688 KB Output is correct
4 Correct 13 ms 13688 KB Output is correct
5 Correct 17 ms 13816 KB Output is correct
6 Correct 66 ms 14456 KB Output is correct
7 Correct 779 ms 21756 KB Output is correct
8 Correct 853 ms 26220 KB Output is correct
9 Correct 489 ms 21868 KB Output is correct
10 Correct 537 ms 21104 KB Output is correct
11 Correct 463 ms 24396 KB Output is correct
12 Correct 479 ms 24172 KB Output is correct
13 Correct 551 ms 25580 KB Output is correct