Submission #712777

#	Time	Username	Problem	Language	Result	Execution time	Memory
712777		four_specks	Synchronization (JOI13_synchronization)	C++17	100 / 100	462 ms	23212 KiB

synchronization

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