Submission #414160

#	Time	Username	Problem	Language	Result	Execution time	Memory
414160		KoD	Inside information (BOI21_servers)	C++17	100 / 100	726 ms	34816 KiB

servers

#include <bits/stdc++.h>

template <class T> using Vec = std::vector<T>;

template <class F> struct RecLambda: private F {
    explicit RecLambda(F&& f): F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator() (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

struct UnionFind {
    Vec<int> par;
    UnionFind(const int n): par(n, -1) {}
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }
    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            par[x] = y;
        }
    }
};

struct Fenwick {
    Vec<int> data;
    Fenwick(const int n): data(n + 1) {}
    void add(int i, const int x) {
        for (i += 1; i < (int) data.size(); i += i & -i) {
            data[i] += x;
        }
    }
    int get(int i) const {
        int x = 0;
        for (; i > 0; i -= i & -i) {
            x += data[i];
        }
        return x;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, K;
    std::cin >> N >> K;
    Vec<int> ans(K);
    Vec<Vec<std::pair<int, int>>> graph(N);
    Vec<Vec<std::pair<int, int>>> detect(N);
    Vec<Vec<std::pair<int, int>>> count(N);
    {
        UnionFind dsu(N);
        int e = 0, q = 0;
        for (int i = 0; i < N + K - 1; ++i) {
            char c;
            std::cin >> c;
            if (c == 'S') {
                int a, b;
                std::cin >> a >> b;
                a -= 1;
                b -= 1;
                graph[a].emplace_back(e, b);
                graph[b].emplace_back(e, a);
                dsu.merge(a, b);
                e += 1;
            } else if (c == 'Q') {
                int u, v;
                std::cin >> u >> v;
                u -= 1;
                v -= 1;
                if (dsu.find(u) == dsu.find(v)) {
                    detect[v].emplace_back(q, u);
                }
                q += 1;
            } else {
                int u;
                std::cin >> u;
                u -= 1;
                count[u].emplace_back(q, e);
                q += 1;
            }
        }
    }
    Vec<char> done(N), to_root(N), from_root(N);
    Vec<int> subtree(N), belong(N, -1);
    const auto setup = RecLambda([&](auto&& dfs, const int u, const int p) -> void {
        subtree[u] = 1;
        for (const auto [e, v]: graph[u]) {
            if (!done[v] and v != p) {
                dfs(v, u);
                subtree[u] += subtree[v];
            }
        }
    });
    const auto reroot = RecLambda([&](auto&& dfs, const int u, const int pe, const int b, Vec<int>& vlist, Vec<int>& elist) -> void {
        belong[u] = b;
        vlist.push_back(u);
        if (from_root[u]) {
            elist.push_back(pe);
        }
        for (const auto [e, v]: graph[u]) {
            if (e != pe and !done[v]) {
                if (e < pe) {
                    if (to_root[u]) {
                        to_root[v] = true;
                    }
                    dfs(v, e, b, vlist, elist);
                } else {
                    if (from_root[u]) {
                        from_root[v] = true;
                    }
                    dfs(v, e, b, vlist, elist);
                }
            }
        }
    });
    const auto centroid = RecLambda([&](auto&& dfs, const int u, const int p, const int whole) -> void {
        for (const auto [e, v]: graph[u]) {
            if (!done[v] and v != p and subtree[v] * 2 > whole) {
                dfs(v, u, whole);
                return;
            }
        }
        done[u] = to_root[u] = from_root[u] = true;
        belong[u] = 0;
        Vec<Vec<int>> vlist, elist;
        vlist.push_back(Vec<int>{u});
        elist.push_back(Vec<int>{-1});
        Vec<int> used;
        used.push_back(-1);
        for (int i = 0; i < (int) graph[u].size(); ++i) {
            const auto v = graph[u][i].second;
            if (!done[v]) {
                to_root[v] = from_root[v] = true;
                const auto b = (int) vlist.size();
                vlist.emplace_back();
                elist.emplace_back();
                reroot(v, graph[u][i].first, b, vlist.back(), elist.back());
                used.push_back(graph[u][i].first);
            }
        }
        Vec<int> all;
        for (int i = 0; i < (int) elist.size(); ++i) {
            for (const auto e: elist[i]) {
                all.push_back(e);
            }
        }
        std::sort(all.begin(), all.end());
        Fenwick fen(all.size());
        for (int i = 0; i < (int) all.size(); ++i) {
            fen.add(i, 1);
        }
        for (int i = 1; i < (int) vlist.size(); ++i) {
            for (const auto e: elist[i]) {
                fen.add(std::lower_bound(all.begin(), all.end(), e) - all.begin(), -1);
            }
            for (const auto v: vlist[i]) {
                for (const auto [k, w]: detect[v]) {
                    if (to_root[v] and ((belong[v] < belong[w] and from_root[w]) or (w == u))) {
                        ans[k] = -1;
                    }
                }
                for (const auto [k, e]: count[v]) {
                    if (to_root[v] and used[i] < e) {
                        ans[k] += fen.get(std::lower_bound(all.begin(), all.end(), e) - all.begin());
                    }
                }
            }
        }
        for (const auto [i, v]: detect[u]) {
            if (from_root[v]) {
                ans[i] = -1;
            }
        }
        for (const auto [i, e]: count[u]) {
            ans[i] += std::lower_bound(all.begin(), all.end(), e) - all.begin();
        }
        for (const auto& l: vlist) {
            for (const auto v: l) {
                to_root[v] = from_root[v] = false;
                belong[v] = -1;
            }
        }
        for (int i = 0; i < (int) graph[u].size(); ++i) {
            const auto v = graph[u][i].second;
            if (!done[v]) {
                setup(v, u);
                dfs(v, u, subtree[v]);
            }
        }
    });
    setup(0, -1);
    centroid(0, -1, N);
    for (const auto x: ans) {
        if (x == 0) {
            std::cout << "no\n";
        } else if (x == -1) {
            std::cout << "yes\n";
        } else {
            std::cout << x << '\n';
        }
    }
    return 0;
}

• 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