oj.uz

Submission #984711

# Submission time Handle Problem Language Result Execution time Memory
984711 2024-05-17T03:17:33 Z Br3ad Synchronization (JOI13_synchronization) C++17
100 / 100
 477 ms 37552 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)

const int N = 2e5 + 5;
const int M = 1e9 + 7; 
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;

struct BIT {
    int sz;
    vector<int> tree;

    BIT(int n) : sz(n+2), tree(n+2, 0) {};

    void add(int pos, int val){
        while(pos < sz){
            tree[pos] += val;
            pos += pos&-pos;
        }
    }

    int sum(int pos){
        int ans = 0;
        while(pos >= 1){
            ans += tree[pos];
            pos -= pos&-pos;
        }
        return ans;
    }
};

vector<vector<int>> adj(N, vector<int>()), par(20, vector<int>(N));
vector<int> to(N), tin(N), tout(N); // For LCA and Binary Lifting
vector<int> info(N, 1), last_sync(N, 0);

vector<pair<int, int>> edge;
bool active[N]{false};

int timer = 1;
void dfs(int cur, int prev){
    tin[cur] = timer++;
    for(int child : adj[cur]){
        if(child == prev) continue;
        to[child] = cur;
        dfs(child, cur);
    }

    tout[cur] = timer++;
}

bool isAncestor(int anc, int child){
    return (tin[anc] < tin[child] && tout[anc] > tout[child]);
}

int find_root(BIT &bit, int child){
    int cur = child, at = bit.sum(tin[child]);
    for(int i = 19; i >= 0; i--){
        int next_cur = par[i][cur];
        if(at - bit.sum(tin[next_cur]) == 0){
            cur = next_cur;
        }
    }
    return cur;
}

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    // ifstream cin();
    // ofstream cout();
    
    int n, m, q;
    cin >> n >> m >> q;

    edge = vector<pair<int, int>>(n);

    for(int i = 1; i <= n-1; i++){
        int a, b;
        cin >> a >> b;

        edge[i] = MP(a, b);

        adj[a].PB(b);
        adj[b].PB(a);
    }

    to[1] = 1;
    dfs(1, -1);

    BIT bit(n*2);
    
    for(int i = 1; i <= n; i++){
        bit.add(tin[i], 1);
        bit.add(tout[i], -1);
    }

    for(int i = 1; i <= n; i++) par[0][i] = to[i];
    for(int i = 1; i < 20; i++){
        for(int j = 1; j <= n; j++){
            par[i][j] = par[i-1][par[i-1][j]];
        }
    }

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

        auto [u, v] = edge[x];
        if(isAncestor(v, u)) swap(u, v);
        // cout << "Modify edge: " << u << ' ' << v << endl;

        if(!active[x]){
            // Activate
            bit.add(tin[v], -1);
            bit.add(tout[v], 1);

            int root = find_root(bit, v);
            info[root] += info[v] - last_sync[v];
        }else {
            // Deactivate
            bit.add(tin[v], 1);
            bit.add(tout[v], -1);

            int root = find_root(bit, u);
            info[v] = info[root];
            last_sync[v] = info[root];
        }

        // cout << "*********************" << endl;
        // for(int i = 1; i <= n; i++){
        //     // cout << "Current info[" << i << "]: " << info[find_root(bit, i)] << endl;
        //     cout << "Current root of " << i << " : " << find_root(bit, i) << endl;
        // }
        // cout << "*********************" << endl;

        active[x] = !active[x];
    }

    while(q--){
        int x;
        cin >> x;
        cout << info[find_root(bit, x)] << endl;
    }
    
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24904 KB Output is correct
2 Correct 11 ms 24652 KB Output is correct
3 Correct 11 ms 24576 KB Output is correct
4 Correct 10 ms 24652 KB Output is correct
5 Correct 10 ms 24704 KB Output is correct
6 Correct 12 ms 24864 KB Output is correct
7 Correct 25 ms 25672 KB Output is correct
8 Correct 27 ms 25420 KB Output is correct
9 Correct 23 ms 25416 KB Output is correct
10 Correct 212 ms 31812 KB Output is correct
11 Correct 304 ms 31808 KB Output is correct
12 Correct 273 ms 36464 KB Output is correct
13 Correct 90 ms 31740 KB Output is correct
14 Correct 135 ms 31332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 32068 KB Output is correct
2 Correct 88 ms 33996 KB Output is correct
3 Correct 88 ms 35932 KB Output is correct
4 Correct 92 ms 35908 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24648 KB Output is correct
2 Correct 10 ms 24652 KB Output is correct
3 Correct 11 ms 24652 KB Output is correct
4 Correct 11 ms 24652 KB Output is correct
5 Correct 11 ms 24652 KB Output is correct
6 Correct 13 ms 24908 KB Output is correct
7 Correct 40 ms 25932 KB Output is correct
8 Correct 477 ms 37552 KB Output is correct
9 Correct 435 ms 37184 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 34468 KB Output is correct
2 Correct 244 ms 37060 KB Output is correct
3 Correct 243 ms 36928 KB Output is correct
4 Correct 249 ms 37068 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24648 KB Output is correct
2 Correct 10 ms 24652 KB Output is correct
3 Correct 11 ms 24652 KB Output is correct
4 Correct 11 ms 24652 KB Output is correct
5 Correct 13 ms 24652 KB Output is correct
6 Correct 39 ms 25420 KB Output is correct
7 Correct 411 ms 32688 KB Output is correct
8 Correct 421 ms 37188 KB Output is correct
9 Correct 233 ms 32836 KB Output is correct
10 Correct 282 ms 32580 KB Output is correct
11 Correct 231 ms 35396 KB Output is correct
12 Correct 227 ms 35136 KB Output is correct
13 Correct 260 ms 37068 KB Output is correct