Submission #1303943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303943		duongquanghai08	Synchronization (JOI13_synchronization)	C++20	100 / 100	217 ms	22588 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; 
vector<int> adj[N];
int up[N][LOG], depth[N], tin[N], tout[N], timer;
int edge_node[N]; 
int bit[N];       
long long ans[N], last[N]; 
bool is_off[N];   

// --- Fenwick Tree (Range Update, Point Query) ---
// Cap nhat: Cong val vao pos
void update(int idx, int val) {
    for (; idx <= n; idx += idx & -idx)
        bit[idx] += val;
}

// Helper function de update range [l, r]
void range_update(int l, int r, int val) {
    update(l, val);
    update(r + 1, -val);
}

// Truy van: Lay gia tri tai pos
int query(int idx) {
    int sum = 0;
    for (; idx > 0; idx -= idx & -idx)
        sum += bit[idx];
    return sum;
}

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;
}

int find_root(int u) {
    int current_off_cnt = query(tin[u]);
    int curr = u;
    for (int i = LOG - 1; i >= 0; i--) {
        int anc = up[curr][i];
        // Neu to tien anc cung thuoc thanh phan lien thong (so canh OFF tu Goc den anc == so canh OFF tu Goc den u)
        // Thi nhay len
        if (anc != 0 && query(tin[anc]) == current_off_cnt) {
            curr = anc;
        }
    }
    return curr;
}

void Solve() {
    if (!(cin >> n >> m >> q)) return;
    
    // Reset cho moi test case neu can thiet (o day chi co 1 test case)
    edges.clear();
    for(int i=1; i<=n; ++i) adj[i].clear();
    timer = 0;
    memset(bit, 0, sizeof(bit));

    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);
    }

    dfs(1, 0);

    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); 
        edge_node[i + 1] = v; 
    }

    // Khoi tao: tat ca cac canh deu OFF
    for (int i = 1; i <= n; i++) {
        ans[i] = 1;      
        last[i] = 0;     
        if (i != 1) {
            // Canh noi i voi cha dang OFF -> +1 vao vung subtree cua i
            range_update(tin[i], tout[i], 1);
            is_off[i] = true;
        }
    }

    for (int j = 1; j <= m; j++) {
        int edge_idx; cin >> edge_idx;
        int v = edge_node[edge_idx]; 
        int u = up[v][0];            

        if (is_off[v]) {
            // OFF -> ON (Noi)
            int root_u = find_root(u);
            ans[root_u] += ans[v] - last[v];
            
            // Xoa danh dau OFF (-1) cho ca cay con cua v
            range_update(tin[v], tout[v], -1);
            is_off[v] = false;
        } 
        else {
            // ON -> OFF (Cat)
            int root_v = find_root(v);
            ans[v] = ans[root_v];
            last[v] = ans[v];
            
            // Them danh dau OFF (+1) cho ca cay con cua v
            range_update(tin[v], tout[v], 1);
            is_off[v] = true;
        }
    }

    for (int k = 1; k <= q; k++) {
        int c; cin >> c;
        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: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40