Submission #572440

#	Time	Username	Problem	Language	Result	Execution time	Memory
572440		Cyanmond	Inside information (BOI21_servers)	C++17	50 / 100	674 ms	31552 KiB

servers

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

constexpr int inf = 1000000100;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)

#define ALL(x) (x).begin(), (x).end()

struct Query {
    bool type;
    int time;
    int v;
};

struct Edge {
    int to;
    int time;
};

int main() {
    int N, K;
    cin >> N >> K;
    vector<tuple<int, int, int>> Q(N + K - 1);
    vector<vector<Edge>> Tree(N);
    vector<int> ans(N + K - 1, -1);
    REP(i, N + K - 1) {
        auto &[c, a, b] = Q[i];
        char s;
        cin >> s >> a;
        --a;
        if (s == 'S') c = 0;
        if (s == 'Q') c = 1;
        if (s == 'C') c = 2;
        if (c != 2) {
            cin >> b;
            --b;
        }
        if (c == 0) {
            Tree[a].push_back({b, i});
            Tree[b].push_back({a, i});
        }
        if (c == 1 and a == b) ans[i] = 1;
    }

    vector<vector<Query>> qv(N);
    REP(i, N + K - 1) {
        const auto &[c, a, b] = Q[i];
        if (c == 0) continue;
        if (c == 1) qv[a].push_back({false, i, b});
        if (c == 2) qv[a].push_back({true, i, 0});
    }

    vector<bool> is_valid(N, true);
    vector<int> subsize(N);
    auto centroid_decompose = [&](auto &&self, const int root, auto &solve) -> void {
        {
            auto dfs = [&](auto &&self, const int v, const int p) -> int {
                subsize[v] = 1;
                for (const auto &[to, dust] : Tree[v]) {
                    if (not is_valid[to]) continue;
                    if (to == p) continue;
                    subsize[v] += self(self, to, v);
                }
                return subsize[v];
            };
            dfs(dfs, root, -1);
        }
        const int count_v = subsize[root];
        int centroid = -1;
        {
            auto dfs = [&](auto &&self, const int v, const int p) -> void {
                bool is_centroid = true;
                for (const auto &[to, dust] : Tree[v]) {
                    if (not is_valid[to]) continue;
                    if (to == p) continue;
                    self(self, to, v);
                    if (subsize[to] > count_v / 2) is_centroid = false;
                }
                if (count_v - subsize[v] > count_v / 2) is_centroid = false;
                if (is_centroid) centroid = v;
            };
            dfs(dfs, root, -1);
        }

        solve(centroid);

        {
            is_valid[centroid] = false;
            vector<vector<int>> vertices;
            for (const auto &[to, dust] : Tree[centroid]) {
                if (not is_valid[to]) continue;
                vertices.push_back({});
                auto dfs = [&](auto &&self, const int v, const int p) -> void {
                    vertices.back().push_back(v);
                    is_valid[v] = false;
                    for (const auto &[to, dust2] : Tree[v]) {
                        if (not is_valid[to]) continue;
                        if (to == p) continue;
                        self(self, to, v);
                    }
                };
                dfs(dfs, to, centroid);
            }
            for (const auto &ver : vertices) {
                for (const int ve : ver) is_valid[ve] = true;
                self(self, ver[0], solve);
                for (const int ve : ver) is_valid[ve] = false;
            }
        }
    };

    vector<bool> is_inc(N), is_dec(N);
    vector<int> froot(N), pa_time(N);

    auto answer_query = [&](const int centroid) {
        {
            auto dfs = [&](auto &&self, const int v, const int p, const int last_time,
                           const int fr) -> void {
                froot[v] = fr;
                pa_time[v] = last_time;
                for (const auto &[to, time] : Tree[v]) {
                    if (not is_valid[to]) continue;
                    if (to == p) continue;
                    if (is_inc[v] and (last_time == -1 or time > last_time)) {
                        is_inc[to] = true;
                    } else {
                        is_inc[to] = false;
                    }
                    if (is_dec[v] and (last_time == -1 or time < last_time)) {
                        is_dec[to] = true;
                    } else {
                        is_dec[to] = false;
                    }
                    self(self, to, v, time, fr == -1 ? to : fr);
                }
            };
            is_inc[centroid] = is_dec[centroid] = true;
            dfs(dfs, centroid, -1, -1, -1);
        }
        {
            auto dfs = [&](auto &&self, const int v, const int p) -> void {
                for (const auto &[type, id, b] : qv[v]) {
                    if (not type) {
                        if (not is_valid[b]) continue;
                        if (froot[v] == froot[b]) continue;
                        if (ans[id] != -1) continue;
                        bool res = is_inc[v] and is_dec[b];
                        res &= (v == centroid ? pa_time[froot[b]] : pa_time[v]) <= id;
                        res &= (v == centroid ? inf : pa_time[froot[v]]) >=
                               (b == centroid ? -1 : pa_time[froot[b]]);
                        ans[id] = res;
                    }
                }
                for (const auto &[to, dust] : Tree[v]) {
                    if (not is_valid[to]) continue;
                    if (to == p) continue;
                    self(self, to, v);
                }
            };
            dfs(dfs, centroid, -1);
        }
    };

    centroid_decompose(centroid_decompose, 0, answer_query);
    REP(i, N + K - 1) {
        if (ans[i] == -1) continue;
        if (get<0>(Q[i]) == 1) {
            cout << (ans[i] ? "yes" : "no") << '\n';
        } else {
            cout << ans[i] << '\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