oj.uz

Submission #414142

# Submission time Handle Problem Language Result Execution time Memory
414142 2021-05-30T06:55:41 Z KoD Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 38228 KB 
#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;
        }
    }
};

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});
        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());
            }
        }
        Vec<int> all;
        for (int i = 0; i < (int) elist.size(); ++i) {
            std::sort(elist[i].begin(), elist[i].end());
            for (const auto e: elist[i]) {
                all.push_back(e);
            }
        }
        std::sort(all.begin(), all.end());
        for (int i = 1; i < (int) vlist.size(); ++i) {
            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]) {
                        ans[k] += std::lower_bound(all.begin(), all.end(), e) - all.begin();                 
                        ans[k] -= std::lower_bound(elist[i].begin(), elist[i].end(), e) - elist[i].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();
        }
        std::cerr << "centroid: " << u << std::endl;
        for (const auto& l: vlist) {
            for (const auto v: l) {
                std::cerr << v << ' ';
                to_root[v] = from_root[v] = false;
                belong[v] = -1;
            }
            std::cerr << std::endl;
        }
        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

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1476 KB Output is correct
2 Correct 160 ms 3372 KB Output is correct
3 Correct 125 ms 4784 KB Output is correct
4 Correct 197 ms 3396 KB Output is correct
5 Correct 216 ms 5220 KB Output is correct
6 Correct 111 ms 4920 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1476 KB Output is correct
2 Correct 160 ms 3372 KB Output is correct
3 Correct 125 ms 4784 KB Output is correct
4 Correct 197 ms 3396 KB Output is correct
5 Correct 216 ms 5220 KB Output is correct
6 Correct 111 ms 4920 KB Output is correct
7 Incorrect 31 ms 1588 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1748 KB Output is correct
2 Correct 1955 ms 38072 KB Output is correct
3 Correct 1963 ms 38072 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1748 KB Output is correct
2 Correct 1955 ms 38072 KB Output is correct
3 Correct 1963 ms 38072 KB Output is correct
4 Incorrect 30 ms 1872 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1540 KB Output is correct
2 Execution timed out 3586 ms 33296 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1540 KB Output is correct
2 Execution timed out 3586 ms 33296 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1612 KB Output is correct
2 Execution timed out 3556 ms 28644 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1612 KB Output is correct
2 Execution timed out 3556 ms 28644 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1432 KB Output is correct
2 Execution timed out 3584 ms 33360 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1432 KB Output is correct
2 Execution timed out 3584 ms 33360 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1456 KB Output is correct
2 Correct 162 ms 3300 KB Output is correct
3 Correct 124 ms 4792 KB Output is correct
4 Correct 207 ms 3332 KB Output is correct
5 Correct 233 ms 5156 KB Output is correct
6 Correct 98 ms 4912 KB Output is correct
7 Correct 32 ms 2708 KB Output is correct
8 Correct 1953 ms 38228 KB Output is correct
9 Correct 1963 ms 38172 KB Output is correct
10 Correct 29 ms 2432 KB Output is correct
11 Execution timed out 3542 ms 32948 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1456 KB Output is correct
2 Correct 162 ms 3300 KB Output is correct
3 Correct 124 ms 4792 KB Output is correct
4 Correct 207 ms 3332 KB Output is correct
5 Correct 233 ms 5156 KB Output is correct
6 Correct 98 ms 4912 KB Output is correct
7 Correct 32 ms 2708 KB Output is correct
8 Correct 1953 ms 38228 KB Output is correct
9 Correct 1963 ms 38172 KB Output is correct
10 Correct 29 ms 2432 KB Output is correct
11 Execution timed out 3542 ms 32948 KB Time limit exceeded
12 Halted 0 ms 0 KB -