oj.uz

Submission #712777

# Submission time Handle Problem Language Result Execution time Memory
712777 2023-03-19T21:09:36 Z four_specks Synchronization (JOI13_synchronization) C++17
100 / 100
 462 ms 23212 KB 
#include <bits/stdc++.h>

using namespace std;

namespace
{
    template <typename Fun>
    struct YCombinator
    {
        template <typename T>
        YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}

        template <typename... Args>
        decltype(auto) operator()(Args &&...args) { return fun(ref(*this), forward<Args>(args)...); }

    private:
        Fun fun;
    };

    template <typename T>
    YCombinator(T &&) -> YCombinator<decay_t<T>>;

} // namespace

template <typename T>
struct Fenwick
{
    Fenwick(int _n) : n(_n), tree(n + 1) {}

    void add(int p, T x)
    {
        for (++p; p <= n; p += p & -p)
            tree[p] += x;
    }

    T sum(int p)
    {
        T ret = 0;
        for (; p; p -= p & -p)
            ret += tree[p];

        return ret;
    }

private:
    int n;
    vector<T> tree;
};

void solve()
{
    int n, m, q;
    cin >> n >> m >> q;

    vector<array<int, 2>> edges(n - 1);
    for (auto &[u, v] : edges)
        cin >> u >> v, --u, --v;

    vector<vector<int>> adj(n);
    for (auto [u, v] : edges)
    {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> tin(n), tout(n);
    vector anc(20, vector<int>(n, -1));

    int timer = 0;
    YCombinator(
        [&](auto self, int u, int p) -> void
        {
            tin[u] = timer++;
            for (int v : adj[u])
            {
                if (v != p)
                {
                    anc[0][v] = u;
                    self(v, u);
                }
            }
            tout[u] = timer;
        })(0, -1);

    for (int s = 1; s < 20; s++)
    {
        for (int u = 0; u < n; u++)
        {
            if (anc[s - 1][u] != -1)
                anc[s][u] = anc[s - 1][anc[s - 1][u]];
        }
    }

    for (auto &[u, v] : edges)
    {
        if (tin[u] > tin[v])
            swap(u, v);
    }

    Fenwick<int> fenw(n);
    for (int u = 0; u < n; u++)
    {
        fenw.add(tin[u], 1);
        fenw.add(tout[u], -1);
    }

    auto rep = [&](int u) -> int
    {
        for (int s = 19; s >= 0; s--)
        {
            if (anc[s][u] != -1)
            {
                if (fenw.sum(tin[u] + 1) - fenw.sum(tin[anc[s][u]] + 1) == 0)
                    u = anc[s][u];
            }
        }

        return u;
    };

    vector<int> x(n, 1), y(n);

    for (int i = 0; i < m; i++)
    {
        int k;
        cin >> k, --k;

        auto [u, v] = edges[k];

        if (fenw.sum(tin[u] + 1) - fenw.sum(tin[v] + 1) == 0)
        {
            y[v] = x[v] = x[rep(u)];
            fenw.add(tin[v], 1);
            fenw.add(tout[v], -1);
        }
        else
        {
            x[rep(u)] += x[v] - y[v];
            fenw.add(tin[v], -1);
            fenw.add(tout[v], 1);
        }
    }

    for (int i = 0; i < q; i++)
    {
        int u;
        cin >> u, --u;

        cout << x[rep(u)] << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 11 ms 2128 KB Output is correct
8 Correct 11 ms 2132 KB Output is correct
9 Correct 11 ms 2132 KB Output is correct
10 Correct 201 ms 18756 KB Output is correct
11 Correct 211 ms 18884 KB Output is correct
12 Correct 373 ms 22440 KB Output is correct
13 Correct 87 ms 18748 KB Output is correct
14 Correct 132 ms 18112 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 18444 KB Output is correct
2 Correct 83 ms 20160 KB Output is correct
3 Correct 106 ms 21804 KB Output is correct
4 Correct 97 ms 21808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 17 ms 2308 KB Output is correct
8 Correct 413 ms 20364 KB Output is correct
9 Correct 441 ms 20368 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 20268 KB Output is correct
2 Correct 151 ms 20560 KB Output is correct
3 Correct 148 ms 20656 KB Output is correct
4 Correct 153 ms 20672 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 15 ms 2180 KB Output is correct
7 Correct 264 ms 19604 KB Output is correct
8 Correct 393 ms 23212 KB Output is correct
9 Correct 91 ms 19892 KB Output is correct
10 Correct 166 ms 19464 KB Output is correct
11 Correct 112 ms 21672 KB Output is correct
12 Correct 112 ms 21664 KB Output is correct
13 Correct 153 ms 22956 KB Output is correct