제출 #483114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483114		Alexandruabcde	동기화 (JOI13_synchronization)	C++14	0 / 100	31 ms	15848 KiB

synchronization

#include <bits/stdc++.h>
#define ub(x) (x&(-x))

using namespace std;

constexpr int NMAX = 1e5 + 5;

struct edge {
    int x, y;
};

edge Edges[NMAX];

int N, M, Q;

vector <int> G[NMAX];

int LengthLog;
int Parent[20][NMAX];
int Lg[NMAX];

int Size[NMAX];
int Poz[NMAX];

int aib[NMAX];

void Update (int poz, int val) {
    for (int i = poz; i <= N; i += ub(i))
        aib[i] += val;
}

int Query (int poz) {
    int ans = 0;

    for (int i = poz; i; i -= ub(i))
        ans += aib[i];

    return ans;
}

void UpdateInterval (int Left, int Right, int val) {
    Update(Left, val);
    Update(Right+1, -val);
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M >> Q;

    for (int i = 1; i < N; ++ i ) {
        cin >> Edges[i].x >> Edges[i].y;
        G[Edges[i].x].push_back(Edges[i].y);
        G[Edges[i].y].push_back(Edges[i].x);
    }

    Lg[1] = 0;
    for (int i = 2; i <= N; ++ i )
        Lg[i] = Lg[i/2] + 1;

    LengthLog = Lg[N];
}

int vf = 0;

void Dfs (int Node, int dad = 0) {
    Parent[Node][0] = dad;
    Size[Node] = 1;
    Poz[Node] = ++vf;

    for (int i = 1; i <= LengthLog; ++ i )
        Parent[Node][i] = Parent[Parent[Node][i-1]][i-1];

    for (auto it : G[Node]) {
        if (it == dad) continue;

        Dfs(it, Node);
        Size[Node] += Size[it];
    }
}

int Sz[NMAX];
int sol[NMAX];

void Precalculare () {
    Dfs(1);

    for (int i = 1; i <= N; ++ i ) {
        sol[i] = 1;
        Sz[i] = 1;

        UpdateInterval(Poz[i], Poz[i] + Size[i] - 1, 1);
    }
}

bool use[NMAX];

int Reprezentant (int Node) {
    for (int i = LengthLog; i >= 0; -- i ) {
        int stramos = Parent[Node][i];

        if (stramos != 0 && Query(Poz[stramos]) == Query(Poz[Node])) Node = stramos;
    }

    return Node;
}

void Solve () {
    for (int i = 1; i <= M; ++ i ) {
        int ind, x, y;
        cin >> ind;

        x = Edges[ind].x;
        y = Edges[ind].y;

        if (Parent[x][0] != y) swap(x, y);

        if (!use[ind]) {
            y = Reprezentant(y);
            Sz[y] += Sz[x];
            sol[y] += Sz[x];

            Sz[x] = 0, sol[x] = 0;

            UpdateInterval(Poz[x], Poz[x] + Size[x] - 1, -1);
        }
        else {
            y = Reprezentant(y);
            sol[x] = sol[y];
            UpdateInterval(Poz[x], Poz[x] + Size[x] - 1, 1);
        }

        use[ind] = 1-use[ind];
    }

    for (int i = 1; i <= Q; ++ i ) {
        int x;
        cin >> x;

        cout << sol[Reprezentant(x)] << '\n';
    }
}

int main () {
    Read();
    Precalculare();
    Solve();

    return 0;
}

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