Submission #572510

#	Time	Username	Problem	Language	Result	Execution time	Memory
572510		Cyanmond	Inside information (BOI21_servers)	C++17	100 / 100	956 ms	31548 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;
};

struct BIT {
    int n;
    vector<int> data;

    BIT(int n_) : n(n_), data(n + 1) {}

    void add(int i, int v) {
        ++i;
        while (i <= n) {
            data[i] += v;
            i += i & -i;
        }
    }

    int fold(int r) {
        int ret = 0;
        while (r != 0) {
            ret += data[r];
            r -= r & -r;
        }
        return ret;
    }
};

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;
        if (c == 2) ans[i] = 0;
    }

    REP(i, N) sort(ALL(Tree[i]), [](Edge a, Edge b) { return a.time < b.time; });

    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, i});
    }

    vector<bool> is_valid(N, true);
    vector<int> subsize(N);
    auto centroid_decompose = [&](auto &&self, const int root, auto &solve1, auto &solve2) -> 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);
        }

        solve1(centroid);
        solve2(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], solve1, solve2);
                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_query1 = [&](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);
        }
    };

    auto answer_query2 = [&](const int centroid) {
        vector<int> press;
        {
            auto dfs = [&](auto &&self, const int v, const int p) -> void {
                for (const auto &[to, time] : Tree[v]) {
                    if (not is_valid[to]) continue;
                    if (to == p) continue;
                    press.push_back(time);
                    self(self, to, v);
                }
            };
            dfs(dfs, centroid, -1);
        }
        sort(ALL(press));
        press.erase(unique(ALL(press)), press.end());
        const int M = (int)size(press);
        BIT rmq(M);
        RVP(i, (int)size(Tree[centroid])) {
            const int r = Tree[centroid][i].to, rt = Tree[centroid][i].time;
            if (not is_valid[r]) continue;
            {
                auto dfs = [&](auto &&self, const int v, const int p) -> void {
                    for (const auto &[type, id, li] : qv[v]) {
                        if (not type) continue;
                        ans[id] += rmq.fold(lower_bound(ALL(press), li) - press.begin());
                        if (li > rt) ++ans[id];
                    }

                    for (const auto &[to, time] : Tree[v]) {
                        if (not is_valid[to]) continue;
                        if (to == p) continue;
                        if (not is_dec[to]) continue;
                        self(self, to, v);
                    }
                };
                dfs(dfs, r, centroid);
            }
            {
                auto dfs = [&](auto &&self, const int v, const int p, int last_time) -> void {
                    rmq.add(lower_bound(ALL(press), last_time) - press.begin(), 1);
                    for (const auto &[to, time] : Tree[v]) {
                        if (not is_valid[to]) continue;
                        if (to == p) continue;
                        if (not is_inc[to]) continue;
                        self(self, to, v, time);
                    }
                };
                dfs(dfs, r, centroid, rt);
            }
        }
        for (const auto &[type, id, li] : qv[centroid]) {
            if (not type) continue;
            ans[id] += rmq.fold(lower_bound(ALL(press), li) - press.begin());
        }
    };

    centroid_decompose(centroid_decompose, 0, answer_query1, answer_query2);
    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] + 1 << '\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