제출 #1303942

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303942		duongquanghai08	동기화 (JOI13_synchronization)	C++20	30 / 100	211 ms	22612 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const int LOG = 18;

int n, m, q;
vector<pair<int, int>> edges; // Luu cac canh de truy xuat
vector<int> adj[N];
int up[N][LOG], depth[N], tin[N], tout[N], timer;
int edge_node[N]; // edge_node[i] = node con trong canh thu i
int bit[N];       // Fenwick tree quan ly so canh OFF
long long ans[N], last[N]; // ans[u]: so thong tin, last[u]: lich su
bool is_off[N];   // Trang thai canh hien tai (quan ly boi node con)

// --- Fenwick Tree ---
void update_bit(int idx, int val) {
    for (; idx <= n; idx += idx & -idx)
        bit[idx] += val;
}

int query_bit(int idx) {
    int sum = 0;
    for (; idx > 0; idx -= idx & -idx)
        sum += bit[idx];
    return sum;
}

// --- DFS & LCA Prep ---
void dfs(int u, int p) {
    tin[u] = ++timer;
    depth[u] = depth[p] + 1;
    up[u][0] = p;
    for (int i = 1; i < LOG; i++)
        up[u][i] = up[up[u][i-1]][i-1];

    for (int v : adj[u]) {
        if (v != p) dfs(v, u);
    }
    tout[u] = timer;
}

// --- Find Representative (Root of component) ---
// Tim to tien cao nhat ma duong di tu do den u toan canh BAT (ON)
int find_root(int u) {
    int current_off_cnt = query_bit(tin[u]);
    int curr = u;
    // Nhay nhi phan len tren
    for (int i = LOG - 1; i >= 0; i--) {
        int anc = up[curr][i];
        if (anc != 0 && query_bit(tin[anc]) == current_off_cnt) {
            curr = anc;
        }
    }
    return curr;
}

void Solve() {
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        edges.push_back({u, v});
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Khoi tao cau truc cay
    dfs(1, 0);

    // Xac dinh chieu cha-con cho cac canh
    for (int i = 0; i < n - 1; i++) {
        int u = edges[i].first;
        int v = edges[i].second;
        if (depth[u] > depth[v]) swap(u, v); 
        // u la cha, v la con
        edge_node[i + 1] = v; // Canh i+1 duoc quan ly boi v
    }

    // Khoi tao ban dau
    for (int i = 1; i <= n; i++) {
        ans[i] = 1;      // Moi may co 1 thong tin
        last[i] = 0;     // Chua tung dong bo
        if (i != 1) {
            update_bit(tin[i], 1); // Danh dau canh noi len cha la OFF (1)
            is_off[i] = true;
        }
    }

    // Xu ly M truy van
    for (int j = 1; j <= m; j++) {
        int edge_idx; cin >> edge_idx;
        int v = edge_node[edge_idx]; // Node con quan ly canh nay
        int u = up[v][0];            // Node cha

        if (is_off[v]) {
            // TH1: Canh dang OFF -> Chuyen thanh ON (Noi)
            
            // 1. Tim dai dien cua nhom cha (u)
            int root_u = find_root(u);
            
            // 2. Cong thong tin moi tu v vao root_u
            // Thong tin moi = Hien tai cua v - Lich su da dong bo truoc do
            ans[root_u] += ans[v] - last[v];
            
            // 3. Cap nhat trang thai canh thanh ON (0)
            update_bit(tin[v], -1); 
            is_off[v] = false;
        } 
        else {
            // TH2: Canh dang ON -> Chuyen thanh OFF (Cat)
            
            // 1. Tim dai dien hien tai cua v (cung la dai dien cua u)
            int root_v = find_root(v);
            
            // 2. v tach ra, lay gia tri hien tai cua ca nhom ve lam cua rieng
            ans[v] = ans[root_v];
            
            // 3. Luu lai lich su de dung cho lan noi sau
            last[v] = ans[v];
            
            // 4. Cap nhat trang thai canh thanh OFF (1)
            update_bit(tin[v], 1);
            is_off[v] = true;
        }
    }

    // Tra loi Q truy van
    for (int k = 1; k <= q; k++) {
        int c; cin >> c;
        // Gia tri cua mot node chinh la gia tri cua dai dien nhom no
        cout << ans[find_root(c)] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    Solve();
    return 0;
}

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