oj.uz

Submission #483117

# Submission time Handle Problem Language Result Execution time Memory
483117 2021-10-27T17:57:47 Z Alexandruabcde Synchronization (JOI13_synchronization) C++14
100 / 100
 312 ms 27720 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[NMAX][20];
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
10.0 / 10.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 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 11 ms 4300 KB Output is correct
8 Correct 13 ms 4336 KB Output is correct
9 Correct 10 ms 4220 KB Output is correct
10 Correct 196 ms 19240 KB Output is correct
11 Correct 148 ms 19192 KB Output is correct
12 Correct 191 ms 26940 KB Output is correct
13 Correct 64 ms 19136 KB Output is correct
14 Correct 152 ms 18664 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 21692 KB Output is correct
2 Correct 70 ms 22756 KB Output is correct
3 Correct 93 ms 26308 KB Output is correct
4 Correct 93 ms 26328 KB Output is correct

Subtask #3
10.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 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 17 ms 5140 KB Output is correct
8 Correct 266 ms 27712 KB Output is correct
9 Correct 260 ms 27720 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 26288 KB Output is correct
2 Correct 161 ms 27320 KB Output is correct
3 Correct 158 ms 27460 KB Output is correct
4 Correct 169 ms 27500 KB Output is correct

Subtask #5
40.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 Correct 1 ms 2636 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 15 ms 4300 KB Output is correct
7 Correct 184 ms 20104 KB Output is correct
8 Correct 312 ms 27712 KB Output is correct
9 Correct 81 ms 20208 KB Output is correct
10 Correct 123 ms 19852 KB Output is correct
11 Correct 96 ms 24040 KB Output is correct
12 Correct 105 ms 24064 KB Output is correct
13 Correct 150 ms 27544 KB Output is correct