oj.uz

Submission #1101800

# Submission time Handle Problem Language Result Execution time Memory
1101800 2024-10-16T20:27:14 Z raphaelp Synchronization (JOI13_synchronization) C++14
100 / 100
 591 ms 37880 KB 
#include <bits/stdc++.h>
using namespace std;
#define LSOne(S) ((S) & (-S))
class Fenwick
{
private:
    vector<int> ft;

public:
    Fenwick(int x) { ft.assign(x + 1, 0); }
    void update(int a, int b, int val)
    {
        b++;
        for (; b; b -= LSOne(b))
            ft[b] += val;
        for (; a; a -= LSOne(a))
            ft[a] -= val;
    }
    int PQ(int x)
    {
        x++;
        int sum = 0;
        for (; x < ft.size(); x += LSOne(x))
            sum += ft[x];
        return sum;
    }
};
void dfs(int x, int p, vector<vector<pair<int, int>>> &AR, vector<int> &depth, vector<int> &id, vector<vector<int>> &bin, vector<int> &l, vector<int> &r, int cur, int &buff)
{
    depth[x] = cur;
    bin[0][x] = p;
    id[x] = buff++;
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i].first == p)
            continue;
        l[AR[x][i].second] = buff;
        dfs(AR[x][i].first, x, AR, depth, id, bin, l, r, cur + 1, buff);
        r[AR[x][i].second] = buff - 1;
    }
}
int main()
{
    int N, Q, K;
    cin >> N >> Q >> K;
    vector<vector<pair<int, int>>> AR(N);
    vector<vector<int>> aretes;
    vector<int> on(N - 1);
    for (int i = 0; i < N - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        aretes.push_back({a, b, 0});
        AR[a].push_back({b, i});
        AR[b].push_back({a, i});
    }
    vector<int> depth(N);
    vector<int> Tab(N, 1);
    vector<vector<int>> bin(log2(N) + 1, vector<int>(N));
    vector<int> l(N - 1), r(N - 1), id(N);
    int buff = 0;
    dfs(0, 0, AR, depth, id, bin, l, r, 0, buff);
    for (int i = 0; i < N - 1; i++)
    {
        if (depth[aretes[i][0]] > depth[aretes[i][1]])
            swap(aretes[i][0], aretes[i][1]);
    }
    for (int i = 1; i <= log2(N); i++)
    {
        for (int j = 0; j < N; j++)
        {
            bin[i][j] = bin[i - 1][bin[i - 1][j]];
        }
    }
    Fenwick FT(N);
    for (int i = 0; i < N - 1; i++)
    {
        if (i < N - 1)
            FT.update(l[i], r[i], 1);
    }
    for (int i = 0; i < Q; i++)
    {
        int x;
        cin >> x;
        if (on[x - 1] == 0)
        {
            x--;
            int a = aretes[x][0], b = aretes[x][1];
            on[x] = 1;
            for (int j = log2(N); j >= 0; j--)
            {
                if (FT.PQ(id[bin[j][a]]) == FT.PQ(id[a]))
                    a = bin[j][a];
            }
            Tab[a] += Tab[b] - aretes[x][2];
            FT.update(l[x], r[x], -1);
        }
        else
        {
            x = abs(x);
            x--;
            on[x] = 0;
            int a = aretes[x][0], b = aretes[x][1];
            for (int j = log2(N); j >= 0; j--)
            {
                if (FT.PQ(id[bin[j][a]]) == FT.PQ(id[a]))
                    a = bin[j][a];
            }
            Tab[b] = Tab[a];
            aretes[x][2] = Tab[a];
            FT.update(l[x], r[x], 1);
        }
    }
    for (int i = 0; i < K; i++)
    {
        int x;
        cin >> x;
        x--;
        for (int j = log2(N); j >= 0; j--)
        {
            if (FT.PQ(id[bin[j][x]]) == FT.PQ(id[x]))
                x = bin[j][x];
        }
        cout << Tab[x] << '\n';
    }
}

Compilation message

synchronization.cpp: In member function 'int Fenwick::PQ(int)':
synchronization.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for (; x < ft.size(); x += LSOne(x))
      |                ~~^~~~~~~~~~~
synchronization.cpp: In function 'void dfs(int, int, std::vector<std::vector<std::pair<int, int> > >&, std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&, int, int&)':
synchronization.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 19 ms 2612 KB Output is correct
8 Correct 19 ms 2448 KB Output is correct
9 Correct 20 ms 2448 KB Output is correct
10 Correct 288 ms 23624 KB Output is correct
11 Correct 285 ms 23704 KB Output is correct
12 Correct 290 ms 37112 KB Output is correct
13 Correct 257 ms 23288 KB Output is correct
14 Correct 199 ms 23032 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 28156 KB Output is correct
2 Correct 223 ms 29688 KB Output is correct
3 Correct 148 ms 36600 KB Output is correct
4 Correct 153 ms 36344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 61 ms 3984 KB Output is correct
8 Correct 548 ms 37880 KB Output is correct
9 Correct 591 ms 37880 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 34932 KB Output is correct
2 Correct 367 ms 37368 KB Output is correct
3 Correct 349 ms 37792 KB Output is correct
4 Correct 358 ms 37624 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 4 ms 816 KB Output is correct
6 Correct 61 ms 2460 KB Output is correct
7 Correct 577 ms 24444 KB Output is correct
8 Correct 496 ms 37732 KB Output is correct
9 Correct 476 ms 24568 KB Output is correct
10 Correct 441 ms 24324 KB Output is correct
11 Correct 467 ms 31240 KB Output is correct
12 Correct 494 ms 31224 KB Output is correct
13 Correct 412 ms 37624 KB Output is correct