제출 #726984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
726984		finn__	Inside information (BOI21_servers)	C++17	100 / 100	650 ms	36924 KiB

servers

#include <bits/stdc++.h>
using namespace std;

template <typename T, int64_t N>
struct FenwickTree
{
    T t[N];

    void update(int64_t i, T x)
    {
        ++i;
        while (i <= N)
            t[i - 1] += x, i += i & -i;
    }

    T prefix_sum(int64_t i)
    {
        ++i;
        T x = 0;
        while (i)
            x += t[i - 1], i -= i & -i;
        return x;
    }
};

constexpr size_t N = 120021;

vector<pair<unsigned, unsigned>> g[N], q1[N], q2[N];
unsigned subtree_size[N], min_time[N], max_time[N], subtree[N];
vector<pair<unsigned, string>> ans;
uint8_t monotonicity[N];
bitset<N> removed;
FenwickTree<int32_t, 2 * N> tree;

unsigned find_centroid(unsigned u, unsigned p, unsigned n)
{
    subtree_size[u] = 1;
    for (auto const &[v, t] : g[u])
        if (!removed[v] && v != p)
        {
            unsigned x = find_centroid(v, u, n);
            if (x != UINT_MAX)
                return x;
            subtree_size[u] += subtree_size[v];
        }
    return subtree_size[u] > n / 2 ? u : UINT_MAX;
}

void trav(unsigned u, unsigned p, unsigned t0, unsigned min_t, unsigned max_t, uint8_t m, unsigned s)
{
    subtree_size[u] = 1;
    monotonicity[u] = m;
    min_time[u] = min_t;
    max_time[u] = max_t;
    subtree[u] = s;
    for (auto const &[v, t] : g[u])
        if (!removed[v] && v != p)
        {
            trav(v, u, t, min(min_t, t), max(max_t, t), m & (t < t0 ? 1 : 2), s);
            subtree_size[u] += subtree_size[v];
        }
}

void answer_queries(unsigned u, unsigned p)
{
    for (size_t i = 0; i < q1[u].size(); ++i)
    {
        auto [v, t] = q1[u][i];
        if (subtree[v] != subtree[u])
        {
            ans.emplace_back(t, ((monotonicity[u] & 2) && (monotonicity[v] & 1) &&
                                 max_time[v] < min_time[u] && t > max_time[u] &&
                                 t > max_time[v])
                                    ? "yes"
                                    : "no");
            swap(q1[u][i], q1[u].back());
            q1[u].pop_back();
            --i;
        }
    }
    for (auto const &[v, t] : g[u])
        if (!removed[v] && v != p)
            answer_queries(v, u);
}

void collect_nodes_queries(unsigned u, unsigned p, vector<pair<unsigned, pair<unsigned, unsigned> *>> &queries,
                           vector<pair<unsigned, unsigned>> &node_times)
{
    if (monotonicity[u] & 2)
        node_times.emplace_back(min_time[u], max_time[u]);
    if (monotonicity[u] & 1)
        for (size_t i = 0; i < q2[u].size(); ++i)
            if (q2[u][i].first > max_time[u])
                queries.emplace_back(max_time[u], &q2[u][i]);
    for (auto const &[v, t] : g[u])
        if (v != p && !removed[v])
            collect_nodes_queries(v, u, queries, node_times);
}

void decompose(unsigned u, unsigned n)
{
    unsigned const c = find_centroid(u, UINT_MAX, n);
    removed[c] = 1;
    monotonicity[c] = 3;
    max_time[c] = 0;
    min_time[c] = UINT_MAX;
    subtree[c] = UINT_MAX;
    vector<pair<unsigned, pair<unsigned, unsigned> *>> queries;
    vector<pair<unsigned, unsigned>> node_times;

    for (auto const &[v, t] : g[c])
        if (!removed[v])
        {
            trav(v, c, t, t, t, 3, v);
            size_t olen1 = queries.size(), olen2 = node_times.size();
            collect_nodes_queries(v, c, queries, node_times);
            sort(node_times.begin() + olen2, node_times.end(), [](auto const &a, auto const &b)
                 { return a.first > b.first; });
            sort(queries.begin() + olen1, queries.end(), [](auto const &a, auto const &b)
                 { return a.first > b.first; });
            size_t j = olen2;
            for (size_t i = olen1; i < queries.size(); ++i)
            {
                while (j < node_times.size() && node_times[j].first > queries[i].first)
                    tree.update(node_times[j].second, 1), ++j;
                queries[i].second->second -= tree.prefix_sum(queries[i].second->first);
            }
            for (size_t i = olen2; i < j; ++i)
                tree.update(node_times[i].second, -1);
        }

    node_times.emplace_back(UINT_MAX, 0);
    for (size_t i = 0; i < q2[c].size(); ++i)
        queries.emplace_back(0, &q2[c][i]);
    sort(node_times.begin(), node_times.end(), [](auto const &a, auto const &b)
         { return a.first > b.first; });
    sort(queries.begin(), queries.end(), [](auto const &a, auto const &b)
         { return a.first > b.first; });

    size_t j = 0;
    for (size_t i = 0; i < queries.size(); ++i)
    {
        while (j < node_times.size() && node_times[j].first > queries[i].first)
            tree.update(node_times[j].second, 1), ++j;
        queries[i].second->second += tree.prefix_sum(queries[i].second->first);
    }
    for (size_t i = 0; i < j; ++i)
        tree.update(node_times[i].second, -1);

    answer_queries(c, UINT_MAX);
    for (auto const &[v, t] : g[c])
        if (!removed[v])
            decompose(v, subtree_size[v]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, k;
    cin >> n >> k;
    for (size_t i = 1; i <= n + k - 1; ++i)
    {
        char c;
        cin >> c;
        if (c == 'S')
        {
            unsigned u, v;
            cin >> u >> v;
            g[u].emplace_back(v, i);
            g[v].emplace_back(u, i);
        }
        else if (c == 'Q')
        {
            unsigned u, v;
            cin >> u >> v;
            if (u == v)
                ans.emplace_back(i, "yes");
            else
                q1[u].emplace_back(v, i);
        }
        else
        {
            unsigned d;
            cin >> d;
            q2[d].emplace_back(i, 0);
        }
    }
    decompose(1, n);
    for (size_t i = 1; i <= n; ++i)
        for (size_t j = 0; j < q2[i].size(); ++j)
            ans.emplace_back(q2[i][j].first, to_string(q2[i][j].second));
    sort(ans.begin(), ans.end());
    assert(ans.size() == k);
    for (auto const &[t, a] : ans)
        cout << a << '\n';
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5