oj.uz

Submission #414149

# Submission time Handle Problem Language Result Execution time Memory
414149 2021-05-30T07:05:15 Z KoD Inside information (BOI21_servers) C++17
50 / 100
 505 ms 32348 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;
        }
    }
};

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});
        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) {
            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]) {
                        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

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1452 KB Output is correct
2 Correct 39 ms 1680 KB Output is correct
3 Correct 41 ms 3304 KB Output is correct
4 Correct 39 ms 1732 KB Output is correct
5 Correct 45 ms 3396 KB Output is correct
6 Correct 42 ms 3376 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1452 KB Output is correct
2 Correct 39 ms 1680 KB Output is correct
3 Correct 41 ms 3304 KB Output is correct
4 Correct 39 ms 1732 KB Output is correct
5 Correct 45 ms 3396 KB Output is correct
6 Correct 42 ms 3376 KB Output is correct
7 Incorrect 36 ms 1468 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 27 ms 1740 KB Output is correct
2 Correct 279 ms 31520 KB Output is correct
3 Correct 314 ms 31528 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1740 KB Output is correct
2 Correct 279 ms 31520 KB Output is correct
3 Correct 314 ms 31528 KB Output is correct
4 Incorrect 27 ms 1688 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1484 KB Output is correct
2 Correct 461 ms 23952 KB Output is correct
3 Correct 433 ms 23700 KB Output is correct
4 Correct 392 ms 24996 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1484 KB Output is correct
2 Correct 461 ms 23952 KB Output is correct
3 Correct 433 ms 23700 KB Output is correct
4 Correct 392 ms 24996 KB Output is correct
5 Incorrect 27 ms 1476 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1632 KB Output is correct
2 Correct 389 ms 20720 KB Output is correct
3 Correct 440 ms 18956 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1632 KB Output is correct
2 Correct 389 ms 20720 KB Output is correct
3 Correct 440 ms 18956 KB Output is correct
4 Incorrect 27 ms 1416 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1472 KB Output is correct
2 Correct 505 ms 23660 KB Output is correct
3 Correct 454 ms 23736 KB Output is correct
4 Correct 367 ms 24952 KB Output is correct
5 Correct 29 ms 1604 KB Output is correct
6 Correct 402 ms 20864 KB Output is correct
7 Correct 406 ms 18908 KB Output is correct
8 Correct 414 ms 19820 KB Output is correct
9 Correct 451 ms 19672 KB Output is correct
10 Correct 486 ms 23276 KB Output is correct
11 Correct 464 ms 22572 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1472 KB Output is correct
2 Correct 505 ms 23660 KB Output is correct
3 Correct 454 ms 23736 KB Output is correct
4 Correct 367 ms 24952 KB Output is correct
5 Correct 29 ms 1604 KB Output is correct
6 Correct 402 ms 20864 KB Output is correct
7 Correct 406 ms 18908 KB Output is correct
8 Correct 414 ms 19820 KB Output is correct
9 Correct 451 ms 19672 KB Output is correct
10 Correct 486 ms 23276 KB Output is correct
11 Correct 464 ms 22572 KB Output is correct
12 Incorrect 27 ms 1472 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1536 KB Output is correct
2 Correct 39 ms 1712 KB Output is correct
3 Correct 44 ms 3268 KB Output is correct
4 Correct 38 ms 1756 KB Output is correct
5 Correct 51 ms 3396 KB Output is correct
6 Correct 42 ms 3472 KB Output is correct
7 Correct 27 ms 1732 KB Output is correct
8 Correct 285 ms 31616 KB Output is correct
9 Correct 278 ms 31580 KB Output is correct
10 Correct 27 ms 1436 KB Output is correct
11 Correct 444 ms 23748 KB Output is correct
12 Correct 498 ms 23708 KB Output is correct
13 Correct 369 ms 24964 KB Output is correct
14 Correct 27 ms 1604 KB Output is correct
15 Correct 380 ms 20784 KB Output is correct
16 Correct 396 ms 18944 KB Output is correct
17 Correct 402 ms 19812 KB Output is correct
18 Correct 493 ms 19808 KB Output is correct
19 Correct 481 ms 23240 KB Output is correct
20 Correct 484 ms 22568 KB Output is correct
21 Correct 309 ms 32348 KB Output is correct
22 Correct 303 ms 28716 KB Output is correct
23 Correct 332 ms 19928 KB Output is correct
24 Correct 341 ms 19816 KB Output is correct
25 Correct 477 ms 30556 KB Output is correct
26 Correct 373 ms 17644 KB Output is correct
27 Correct 347 ms 17936 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1536 KB Output is correct
2 Correct 39 ms 1712 KB Output is correct
3 Correct 44 ms 3268 KB Output is correct
4 Correct 38 ms 1756 KB Output is correct
5 Correct 51 ms 3396 KB Output is correct
6 Correct 42 ms 3472 KB Output is correct
7 Correct 27 ms 1732 KB Output is correct
8 Correct 285 ms 31616 KB Output is correct
9 Correct 278 ms 31580 KB Output is correct
10 Correct 27 ms 1436 KB Output is correct
11 Correct 444 ms 23748 KB Output is correct
12 Correct 498 ms 23708 KB Output is correct
13 Correct 369 ms 24964 KB Output is correct
14 Correct 27 ms 1604 KB Output is correct
15 Correct 380 ms 20784 KB Output is correct
16 Correct 396 ms 18944 KB Output is correct
17 Correct 402 ms 19812 KB Output is correct
18 Correct 493 ms 19808 KB Output is correct
19 Correct 481 ms 23240 KB Output is correct
20 Correct 484 ms 22568 KB Output is correct
21 Correct 309 ms 32348 KB Output is correct
22 Correct 303 ms 28716 KB Output is correct
23 Correct 332 ms 19928 KB Output is correct
24 Correct 341 ms 19816 KB Output is correct
25 Correct 477 ms 30556 KB Output is correct
26 Correct 373 ms 17644 KB Output is correct
27 Correct 347 ms 17936 KB Output is correct
28 Incorrect 27 ms 1520 KB Extra information in the output file
29 Halted 0 ms 0 KB -