oj.uz

Submission #414160

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

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1784 KB Output is correct
2 Correct 40 ms 2008 KB Output is correct
3 Correct 53 ms 3580 KB Output is correct
4 Correct 39 ms 2028 KB Output is correct
5 Correct 46 ms 3652 KB Output is correct
6 Correct 46 ms 3812 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1784 KB Output is correct
2 Correct 40 ms 2008 KB Output is correct
3 Correct 53 ms 3580 KB Output is correct
4 Correct 39 ms 2028 KB Output is correct
5 Correct 46 ms 3652 KB Output is correct
6 Correct 46 ms 3812 KB Output is correct
7 Correct 31 ms 1640 KB Output is correct
8 Correct 45 ms 3476 KB Output is correct
9 Correct 41 ms 4256 KB Output is correct
10 Correct 45 ms 3524 KB Output is correct
11 Correct 53 ms 4576 KB Output is correct
12 Correct 43 ms 4564 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1988 KB Output is correct
2 Correct 282 ms 32560 KB Output is correct
3 Correct 287 ms 32620 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1988 KB Output is correct
2 Correct 282 ms 32560 KB Output is correct
3 Correct 287 ms 32620 KB Output is correct
4 Correct 28 ms 1832 KB Output is correct
5 Correct 281 ms 34600 KB Output is correct
6 Correct 202 ms 32348 KB Output is correct
7 Correct 214 ms 32868 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1784 KB Output is correct
2 Correct 466 ms 24284 KB Output is correct
3 Correct 447 ms 24208 KB Output is correct
4 Correct 411 ms 25588 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1784 KB Output is correct
2 Correct 466 ms 24284 KB Output is correct
3 Correct 447 ms 24208 KB Output is correct
4 Correct 411 ms 25588 KB Output is correct
5 Correct 32 ms 1464 KB Output is correct
6 Correct 482 ms 27080 KB Output is correct
7 Correct 425 ms 28372 KB Output is correct
8 Correct 452 ms 26412 KB Output is correct
9 Correct 445 ms 26312 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1876 KB Output is correct
2 Correct 387 ms 21240 KB Output is correct
3 Correct 428 ms 19460 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1876 KB Output is correct
2 Correct 387 ms 21240 KB Output is correct
3 Correct 428 ms 19460 KB Output is correct
4 Correct 27 ms 1580 KB Output is correct
5 Correct 439 ms 24120 KB Output is correct
6 Correct 409 ms 22304 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1824 KB Output is correct
2 Correct 458 ms 24184 KB Output is correct
3 Correct 501 ms 24168 KB Output is correct
4 Correct 382 ms 25424 KB Output is correct
5 Correct 28 ms 1844 KB Output is correct
6 Correct 410 ms 21556 KB Output is correct
7 Correct 417 ms 19464 KB Output is correct
8 Correct 434 ms 20396 KB Output is correct
9 Correct 474 ms 20188 KB Output is correct
10 Correct 495 ms 23728 KB Output is correct
11 Correct 485 ms 23068 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1824 KB Output is correct
2 Correct 458 ms 24184 KB Output is correct
3 Correct 501 ms 24168 KB Output is correct
4 Correct 382 ms 25424 KB Output is correct
5 Correct 28 ms 1844 KB Output is correct
6 Correct 410 ms 21556 KB Output is correct
7 Correct 417 ms 19464 KB Output is correct
8 Correct 434 ms 20396 KB Output is correct
9 Correct 474 ms 20188 KB Output is correct
10 Correct 495 ms 23728 KB Output is correct
11 Correct 485 ms 23068 KB Output is correct
12 Correct 28 ms 1564 KB Output is correct
13 Correct 495 ms 27100 KB Output is correct
14 Correct 447 ms 28388 KB Output is correct
15 Correct 451 ms 26332 KB Output is correct
16 Correct 450 ms 26364 KB Output is correct
17 Correct 35 ms 2244 KB Output is correct
18 Correct 407 ms 24196 KB Output is correct
19 Correct 418 ms 22228 KB Output is correct
20 Correct 460 ms 23280 KB Output is correct
21 Correct 486 ms 23276 KB Output is correct
22 Correct 500 ms 26120 KB Output is correct
23 Correct 672 ms 26344 KB Output is correct
24 Correct 614 ms 26168 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1712 KB Output is correct
2 Correct 40 ms 2012 KB Output is correct
3 Correct 48 ms 3520 KB Output is correct
4 Correct 39 ms 2028 KB Output is correct
5 Correct 49 ms 3732 KB Output is correct
6 Correct 43 ms 3696 KB Output is correct
7 Correct 28 ms 2060 KB Output is correct
8 Correct 262 ms 32608 KB Output is correct
9 Correct 270 ms 32612 KB Output is correct
10 Correct 28 ms 1740 KB Output is correct
11 Correct 507 ms 24196 KB Output is correct
12 Correct 450 ms 24208 KB Output is correct
13 Correct 383 ms 25480 KB Output is correct
14 Correct 28 ms 1824 KB Output is correct
15 Correct 405 ms 21268 KB Output is correct
16 Correct 404 ms 19456 KB Output is correct
17 Correct 438 ms 20308 KB Output is correct
18 Correct 519 ms 20184 KB Output is correct
19 Correct 500 ms 23780 KB Output is correct
20 Correct 481 ms 23128 KB Output is correct
21 Correct 290 ms 33276 KB Output is correct
22 Correct 294 ms 29548 KB Output is correct
23 Correct 338 ms 20456 KB Output is correct
24 Correct 332 ms 20412 KB Output is correct
25 Correct 480 ms 31304 KB Output is correct
26 Correct 409 ms 18540 KB Output is correct
27 Correct 350 ms 18432 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1712 KB Output is correct
2 Correct 40 ms 2012 KB Output is correct
3 Correct 48 ms 3520 KB Output is correct
4 Correct 39 ms 2028 KB Output is correct
5 Correct 49 ms 3732 KB Output is correct
6 Correct 43 ms 3696 KB Output is correct
7 Correct 28 ms 2060 KB Output is correct
8 Correct 262 ms 32608 KB Output is correct
9 Correct 270 ms 32612 KB Output is correct
10 Correct 28 ms 1740 KB Output is correct
11 Correct 507 ms 24196 KB Output is correct
12 Correct 450 ms 24208 KB Output is correct
13 Correct 383 ms 25480 KB Output is correct
14 Correct 28 ms 1824 KB Output is correct
15 Correct 405 ms 21268 KB Output is correct
16 Correct 404 ms 19456 KB Output is correct
17 Correct 438 ms 20308 KB Output is correct
18 Correct 519 ms 20184 KB Output is correct
19 Correct 500 ms 23780 KB Output is correct
20 Correct 481 ms 23128 KB Output is correct
21 Correct 290 ms 33276 KB Output is correct
22 Correct 294 ms 29548 KB Output is correct
23 Correct 338 ms 20456 KB Output is correct
24 Correct 332 ms 20412 KB Output is correct
25 Correct 480 ms 31304 KB Output is correct
26 Correct 409 ms 18540 KB Output is correct
27 Correct 350 ms 18432 KB Output is correct
28 Correct 29 ms 1668 KB Output is correct
29 Correct 44 ms 3540 KB Output is correct
30 Correct 45 ms 4280 KB Output is correct
31 Correct 46 ms 3528 KB Output is correct
32 Correct 50 ms 4552 KB Output is correct
33 Correct 41 ms 4548 KB Output is correct
34 Correct 28 ms 2508 KB Output is correct
35 Correct 273 ms 34640 KB Output is correct
36 Correct 192 ms 32460 KB Output is correct
37 Correct 193 ms 32720 KB Output is correct
38 Correct 28 ms 2356 KB Output is correct
39 Correct 448 ms 27080 KB Output is correct
40 Correct 415 ms 28400 KB Output is correct
41 Correct 470 ms 26352 KB Output is correct
42 Correct 462 ms 26404 KB Output is correct
43 Correct 28 ms 2372 KB Output is correct
44 Correct 421 ms 24248 KB Output is correct
45 Correct 417 ms 22248 KB Output is correct
46 Correct 453 ms 23276 KB Output is correct
47 Correct 481 ms 23312 KB Output is correct
48 Correct 521 ms 26016 KB Output is correct
49 Correct 726 ms 26580 KB Output is correct
50 Correct 628 ms 26220 KB Output is correct
51 Correct 245 ms 34816 KB Output is correct
52 Correct 214 ms 33376 KB Output is correct
53 Correct 191 ms 33224 KB Output is correct
54 Correct 203 ms 33620 KB Output is correct
55 Correct 213 ms 33748 KB Output is correct
56 Correct 332 ms 22536 KB Output is correct
57 Correct 450 ms 31948 KB Output is correct
58 Correct 492 ms 21892 KB Output is correct
59 Correct 375 ms 21440 KB Output is correct