oj.uz

Submission #220742

# Submission time Handle Problem Language Result Execution time Memory
220742 2020-04-08T14:08:02 Z tictaccat Synchronization (JOI13_synchronization) C++14
30 / 100
 556 ms 25308 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 c;
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);

vector<int> tr(MAX);

void dfs(int u) {
    explored[u] = true;
    pre[u] = c++;
    for (int v: adj[u]) {
        if (explored[v]) continue;
        p[v] = u;
        dep[v] = dep[u]+1;
        dfs(v);
    }
    post[u] = c-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]--;
    }

    cin >> C;
    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);
        if (active[d]) {
         //   cout << "adding " << u+1 << " " << v+1 << "\n";
           // cout << num_edges(5-1) << "\n";
            int rtV = find_root(v);
            int rtU = find_root(u);
          //  cout << rtU+1 << " " << rtV+1 << "\n";
            a[rtV] += a[rtU];
            a[rtU] = 0;
            add_edge(u, 1);
        }
        if (!active[d]) {
            //cout << "removing " << u+1 << " " << v+1 << "\n";
            add_edge(u, -1);
        }
    }
    

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


    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 13304 KB Output is correct
2 Correct 12 ms 13304 KB Output is correct
3 Correct 12 ms 13304 KB Output is correct
4 Correct 12 ms 13304 KB Output is correct
5 Correct 13 ms 13304 KB Output is correct
6 Correct 14 ms 13304 KB Output is correct
7 Correct 40 ms 13944 KB Output is correct
8 Correct 48 ms 14064 KB Output is correct
9 Correct 41 ms 13944 KB Output is correct
10 Correct 526 ms 20572 KB Output is correct
11 Correct 556 ms 20460 KB Output is correct
12 Correct 486 ms 23148 KB Output is correct
13 Correct 349 ms 20460 KB Output is correct
14 Correct 398 ms 19436 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 22692 KB Output is correct
2 Correct 290 ms 21360 KB Output is correct
3 Correct 280 ms 23660 KB Output is correct
4 Correct 266 ms 22984 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 13304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 516 ms 25308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 13304 KB Output isn't correct
2 Halted 0 ms 0 KB -