Submission #1101800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101800		raphaelp	Synchronization (JOI13_synchronization)	C++14	100 / 100	591 ms	37880 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40