oj.uz

Submission #414148

# Submission time Handle Problem Language Result Execution time Memory
414148 2021-05-30T07:02:25 Z KoD Inside information (BOI21_servers) C++17
50 / 100
 525 ms 33748 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 fold(const int l, const int r) const {
        return get(r) - get(l);
    }
};

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.fold(0, 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 27 ms 2244 KB Output is correct
2 Correct 41 ms 3096 KB Output is correct
3 Correct 42 ms 4692 KB Output is correct
4 Correct 41 ms 3076 KB Output is correct
5 Correct 45 ms 4796 KB Output is correct
6 Correct 44 ms 4796 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2244 KB Output is correct
2 Correct 41 ms 3096 KB Output is correct
3 Correct 42 ms 4692 KB Output is correct
4 Correct 41 ms 3076 KB Output is correct
5 Correct 45 ms 4796 KB Output is correct
6 Correct 44 ms 4796 KB Output is correct
7 Incorrect 33 ms 1552 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 28 ms 2500 KB Output is correct
2 Correct 281 ms 33044 KB Output is correct
3 Correct 271 ms 32976 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2500 KB Output is correct
2 Correct 281 ms 33044 KB Output is correct
3 Correct 271 ms 32976 KB Output is correct
4 Incorrect 27 ms 1860 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 2248 KB Output is correct
2 Correct 477 ms 25112 KB Output is correct
3 Correct 452 ms 25120 KB Output is correct
4 Correct 373 ms 26352 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2248 KB Output is correct
2 Correct 477 ms 25112 KB Output is correct
3 Correct 452 ms 25120 KB Output is correct
4 Correct 373 ms 26352 KB Output is correct
5 Incorrect 28 ms 1568 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 29 ms 2220 KB Output is correct
2 Correct 384 ms 22072 KB Output is correct
3 Correct 394 ms 20332 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2220 KB Output is correct
2 Correct 384 ms 22072 KB Output is correct
3 Correct 394 ms 20332 KB Output is correct
4 Incorrect 27 ms 1596 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 2232 KB Output is correct
2 Correct 452 ms 25128 KB Output is correct
3 Correct 448 ms 25116 KB Output is correct
4 Correct 371 ms 26348 KB Output is correct
5 Correct 28 ms 2444 KB Output is correct
6 Correct 373 ms 22144 KB Output is correct
7 Correct 424 ms 20460 KB Output is correct
8 Correct 403 ms 21320 KB Output is correct
9 Correct 457 ms 21152 KB Output is correct
10 Correct 484 ms 24648 KB Output is correct
11 Correct 525 ms 23984 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2232 KB Output is correct
2 Correct 452 ms 25128 KB Output is correct
3 Correct 448 ms 25116 KB Output is correct
4 Correct 371 ms 26348 KB Output is correct
5 Correct 28 ms 2444 KB Output is correct
6 Correct 373 ms 22144 KB Output is correct
7 Correct 424 ms 20460 KB Output is correct
8 Correct 403 ms 21320 KB Output is correct
9 Correct 457 ms 21152 KB Output is correct
10 Correct 484 ms 24648 KB Output is correct
11 Correct 525 ms 23984 KB Output is correct
12 Incorrect 30 ms 1592 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 28 ms 2164 KB Output is correct
2 Correct 39 ms 3092 KB Output is correct
3 Correct 41 ms 4676 KB Output is correct
4 Correct 39 ms 3060 KB Output is correct
5 Correct 45 ms 4900 KB Output is correct
6 Correct 47 ms 4736 KB Output is correct
7 Correct 28 ms 2636 KB Output is correct
8 Correct 268 ms 33068 KB Output is correct
9 Correct 272 ms 33088 KB Output is correct
10 Correct 27 ms 2372 KB Output is correct
11 Correct 438 ms 25064 KB Output is correct
12 Correct 433 ms 25064 KB Output is correct
13 Correct 385 ms 26356 KB Output is correct
14 Correct 27 ms 2500 KB Output is correct
15 Correct 380 ms 22060 KB Output is correct
16 Correct 384 ms 20328 KB Output is correct
17 Correct 394 ms 21220 KB Output is correct
18 Correct 431 ms 21088 KB Output is correct
19 Correct 481 ms 24624 KB Output is correct
20 Correct 459 ms 23988 KB Output is correct
21 Correct 285 ms 33748 KB Output is correct
22 Correct 283 ms 30088 KB Output is correct
23 Correct 337 ms 21356 KB Output is correct
24 Correct 336 ms 21280 KB Output is correct
25 Correct 475 ms 32136 KB Output is correct
26 Correct 371 ms 19180 KB Output is correct
27 Correct 342 ms 19436 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2164 KB Output is correct
2 Correct 39 ms 3092 KB Output is correct
3 Correct 41 ms 4676 KB Output is correct
4 Correct 39 ms 3060 KB Output is correct
5 Correct 45 ms 4900 KB Output is correct
6 Correct 47 ms 4736 KB Output is correct
7 Correct 28 ms 2636 KB Output is correct
8 Correct 268 ms 33068 KB Output is correct
9 Correct 272 ms 33088 KB Output is correct
10 Correct 27 ms 2372 KB Output is correct
11 Correct 438 ms 25064 KB Output is correct
12 Correct 433 ms 25064 KB Output is correct
13 Correct 385 ms 26356 KB Output is correct
14 Correct 27 ms 2500 KB Output is correct
15 Correct 380 ms 22060 KB Output is correct
16 Correct 384 ms 20328 KB Output is correct
17 Correct 394 ms 21220 KB Output is correct
18 Correct 431 ms 21088 KB Output is correct
19 Correct 481 ms 24624 KB Output is correct
20 Correct 459 ms 23988 KB Output is correct
21 Correct 285 ms 33748 KB Output is correct
22 Correct 283 ms 30088 KB Output is correct
23 Correct 337 ms 21356 KB Output is correct
24 Correct 336 ms 21280 KB Output is correct
25 Correct 475 ms 32136 KB Output is correct
26 Correct 371 ms 19180 KB Output is correct
27 Correct 342 ms 19436 KB Output is correct
28 Incorrect 27 ms 1564 KB Extra information in the output file
29 Halted 0 ms 0 KB -