oj.uz

Submission #712761

# Submission time Handle Problem Language Result Execution time Memory
712761 2023-03-19T18:45:32 Z four_specks Synchronization (JOI13_synchronization) C++17
30 / 100
 321 ms 23320 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(u, 1);

    auto rep = [&](int u) -> int
    {
        for (int s = 19; s >= 0; s--)
        {
            if (anc[s][u] != -1)
            {
                if (fenw.sum(u + 1) - fenw.sum(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(v + 1) - fenw.sum(v) == 0)
        {
            y[v] = x[v] = x[rep(u)];
            fenw.add(v, 1);
        }
        else
        {
            x[rep(u)] += x[v] - y[v];
            fenw.add(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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 20376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 328 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 536 KB Output is correct
7 Correct 16 ms 2512 KB Output is correct
8 Correct 314 ms 23320 KB Output is correct
9 Correct 321 ms 23236 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 23168 KB Output is correct
2 Correct 138 ms 22788 KB Output is correct
3 Correct 131 ms 23036 KB Output is correct
4 Correct 137 ms 23072 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -