Submission #726959

#	Time	Username	Problem	Language	Result	Execution time	Memory
726959		finn__	Inside information (BOI21_servers)	C++17	50 / 100	372 ms	34704 KiB

servers

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

constexpr size_t N = 120001;

vector<pair<unsigned, unsigned>> g[N], q1[N];
vector<unsigned> 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;

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 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;
    for (auto const &[v, t] : g[c])
        if (!removed[v])
            trav(v, c, t, t, t, 3, v);
    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].push_back(i);
        }
    }
    decompose(1, n);
    sort(ans.begin(), ans.end());
    for (auto const &[t, a] : ans)
        cout << a << '\n';
}

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