제출 #1327609

#제출 시각아이디문제언어결과실행 시간메모리
1327609sh_qaxxorov_571동기화 (JOI13_synchronization)C++20
30 / 100
181 ms20732 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
const int MAXLOG = 18;

vector<int> adj[MAXN];
int X[MAXN], Y[MAXN], st[MAXN], en[MAXN], timer;
int up[MAXN][MAXLOG];
int ans[MAXN], last_sync[MAXN];
bool active[MAXN];
int bit[MAXN];

// Fenwick Tree (BIT) işlemleri
void update(int i, int val) {
    for (; i < MAXN; i += i & -i) bit[i] += val;
}

int query(int i) {
    int res = 0;
    for (; i > 0; i -= i & -i) res += bit[i];
    return res;
}

// Ağacı düzleştirme (Euler Tour)
void dfs(int u, int p) {
    st[u] = ++timer;
    up[u][0] = p;
    for (int i = 1; i < MAXLOG; i++)
        up[u][i] = up[up[u][i-1]][i-1];
    
    for (int v : adj[u]) {
        if (v != p) dfs(v, u);
    }
    en[u] = timer;
}

// Mevcut bağlı bileşenin kökünü (en üst aktif ata) bulma
int find_root(int u) {
    int curr = u;
    for (int i = MAXLOG - 1; i >= 0; i--) {
        int ancestor = up[curr][i];
        if (ancestor != 0 && (query(st[u]) - query(st[ancestor])) == 0) {
            curr = ancestor;
        }
    }
    return curr;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, Q;
    cin >> N >> M >> Q;

    for (int i = 1; i < N; i++) {
        cin >> X[i] >> Y[i];
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    dfs(1, 0);

    // Her sunucu başlangıçta sadece kendi bilgisine sahip
    for (int i = 1; i <= N; i++) ans[i] = 1;

    // Tüm kenarları pasif (kopuk) olarak işaretle
    for (int i = 1; i <= N; i++) update(st[i], 1);

    for (int j = 0; j < M; j++) {
        int d;
        cin >> d;
        int u = X[d], v = Y[d];
        // u her zaman v'nin çocuğu olacak şekilde ayarla
        if (up[u][0] != v) swap(u, v);

        if (!active[d]) {
            // Kenar bağlanıyor
            int root_v = find_root(v);
            int root_u = u; // u zaten kendi başına bir köktü
            
            // Bilgileri birleştir (v'nin bağlı olduğu bileşene u'yu ekle)
            ans[root_v] += ans[root_u] - last_sync[d];
            update(st[u], -1); // Kenarı Fenwick Tree'de aktif yap (değer 0 olur)
            active[d] = true;
        } else {
            // Kenar kopuyor
            int root_v = find_root(v);
            ans[u] = ans[root_v]; // u alt ağacı mevcut bilgiyi korur
            last_sync[d] = ans[u]; // Kopma anındaki bilgiyi kaydet
            update(st[u], 1); // Kenarı Fenwick Tree'de pasif yap
            active[d] = false;
        }
    }

    for (int k = 0; k < Q; k++) {
        int c;
        cin >> c;
        cout << ans[find_root(c)] << "\n";
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...