oj.uz

Submission #863530

# Submission time Handle Problem Language Result Execution time Memory
863530 2023-10-20T14:12:18 Z lolismek Synchronization (JOI13_synchronization) C++14
100 / 100
 421 ms 25904 KB 
#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(lin[node].first) == AIB::query(lin[dp[node][i]].first)){
            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)] << '\n';
    }

    return 0;
}

/*
5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
1
4
5
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8640 KB Output is correct
6 Correct 2 ms 8536 KB Output is correct
7 Correct 13 ms 9052 KB Output is correct
8 Correct 13 ms 9048 KB Output is correct
9 Correct 16 ms 9052 KB Output is correct
10 Correct 151 ms 18772 KB Output is correct
11 Correct 155 ms 19440 KB Output is correct
12 Correct 212 ms 25112 KB Output is correct
13 Correct 101 ms 18632 KB Output is correct
14 Correct 121 ms 18164 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 19900 KB Output is correct
2 Correct 105 ms 21588 KB Output is correct
3 Correct 111 ms 24400 KB Output is correct
4 Correct 112 ms 24444 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8648 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 30 ms 9860 KB Output is correct
8 Correct 368 ms 25684 KB Output is correct
9 Correct 418 ms 25732 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 23456 KB Output is correct
2 Correct 278 ms 25812 KB Output is correct
3 Correct 279 ms 25684 KB Output is correct
4 Correct 282 ms 25484 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 4 ms 8540 KB Output is correct
6 Correct 27 ms 9048 KB Output is correct
7 Correct 314 ms 19948 KB Output is correct
8 Correct 377 ms 25904 KB Output is correct
9 Correct 270 ms 19884 KB Output is correct
10 Correct 252 ms 19620 KB Output is correct
11 Correct 258 ms 23120 KB Output is correct
12 Correct 249 ms 23032 KB Output is correct
13 Correct 278 ms 25684 KB Output is correct