oj.uz

Submission #483114

# Submission time Handle Problem Language Result Execution time Memory
483114 2021-10-27T17:33:15 Z Alexandruabcde Synchronization (JOI13_synchronization) C++14
0 / 100
 31 ms 15848 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Runtime error 4 ms 5196 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 15848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Runtime error 4 ms 5452 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 15448 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Runtime error 4 ms 5272 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -