oj.uz

Submission #414144

# Submission time Handle Problem Language Result Execution time Memory
414144 2021-05-30T06:57:03 Z KoD Inside information (BOI21_servers) C++17
50 / 100
 485 ms 35288 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();
        }
        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 28 ms 1476 KB Output is correct
2 Correct 39 ms 2100 KB Output is correct
3 Correct 41 ms 3492 KB Output is correct
4 Correct 39 ms 1900 KB Output is correct
5 Correct 47 ms 3752 KB Output is correct
6 Correct 44 ms 3700 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 39 ms 2100 KB Output is correct
3 Correct 41 ms 3492 KB Output is correct
4 Correct 39 ms 1900 KB Output is correct
5 Correct 47 ms 3752 KB Output is correct
6 Correct 44 ms 3700 KB Output is correct
7 Incorrect 29 ms 1560 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 1732 KB Output is correct
2 Correct 241 ms 31800 KB Output is correct
3 Correct 257 ms 31980 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1732 KB Output is correct
2 Correct 241 ms 31800 KB Output is correct
3 Correct 257 ms 31980 KB Output is correct
4 Incorrect 28 ms 1752 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 27 ms 1436 KB Output is correct
2 Correct 458 ms 23960 KB Output is correct
3 Correct 442 ms 27068 KB Output is correct
4 Correct 325 ms 27756 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1436 KB Output is correct
2 Correct 458 ms 23960 KB Output is correct
3 Correct 442 ms 27068 KB Output is correct
4 Correct 325 ms 27756 KB Output is correct
5 Incorrect 28 ms 1612 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 1604 KB Output is correct
2 Correct 352 ms 20424 KB Output is correct
3 Correct 385 ms 22260 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1604 KB Output is correct
2 Correct 352 ms 20424 KB Output is correct
3 Correct 385 ms 22260 KB Output is correct
4 Incorrect 28 ms 1592 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 27 ms 1540 KB Output is correct
2 Correct 485 ms 23984 KB Output is correct
3 Correct 436 ms 26988 KB Output is correct
4 Correct 336 ms 27868 KB Output is correct
5 Correct 27 ms 2432 KB Output is correct
6 Correct 357 ms 23524 KB Output is correct
7 Correct 395 ms 22240 KB Output is correct
8 Correct 392 ms 23112 KB Output is correct
9 Correct 425 ms 22880 KB Output is correct
10 Correct 447 ms 26472 KB Output is correct
11 Correct 451 ms 25784 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1540 KB Output is correct
2 Correct 485 ms 23984 KB Output is correct
3 Correct 436 ms 26988 KB Output is correct
4 Correct 336 ms 27868 KB Output is correct
5 Correct 27 ms 2432 KB Output is correct
6 Correct 357 ms 23524 KB Output is correct
7 Correct 395 ms 22240 KB Output is correct
8 Correct 392 ms 23112 KB Output is correct
9 Correct 425 ms 22880 KB Output is correct
10 Correct 447 ms 26472 KB Output is correct
11 Correct 451 ms 25784 KB Output is correct
12 Incorrect 28 ms 1508 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 1524 KB Output is correct
2 Correct 42 ms 2020 KB Output is correct
3 Correct 42 ms 3524 KB Output is correct
4 Correct 39 ms 2020 KB Output is correct
5 Correct 49 ms 3772 KB Output is correct
6 Correct 42 ms 3620 KB Output is correct
7 Correct 28 ms 2004 KB Output is correct
8 Correct 240 ms 31840 KB Output is correct
9 Correct 237 ms 31824 KB Output is correct
10 Correct 28 ms 1756 KB Output is correct
11 Correct 428 ms 24048 KB Output is correct
12 Correct 434 ms 27048 KB Output is correct
13 Correct 325 ms 27756 KB Output is correct
14 Correct 28 ms 2500 KB Output is correct
15 Correct 362 ms 23532 KB Output is correct
16 Correct 377 ms 22268 KB Output is correct
17 Correct 390 ms 23148 KB Output is correct
18 Correct 415 ms 22888 KB Output is correct
19 Correct 461 ms 26604 KB Output is correct
20 Correct 449 ms 25784 KB Output is correct
21 Correct 263 ms 35288 KB Output is correct
22 Correct 273 ms 31552 KB Output is correct
23 Correct 342 ms 23072 KB Output is correct
24 Correct 328 ms 23052 KB Output is correct
25 Correct 477 ms 33852 KB Output is correct
26 Correct 375 ms 21484 KB Output is correct
27 Correct 340 ms 21376 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1524 KB Output is correct
2 Correct 42 ms 2020 KB Output is correct
3 Correct 42 ms 3524 KB Output is correct
4 Correct 39 ms 2020 KB Output is correct
5 Correct 49 ms 3772 KB Output is correct
6 Correct 42 ms 3620 KB Output is correct
7 Correct 28 ms 2004 KB Output is correct
8 Correct 240 ms 31840 KB Output is correct
9 Correct 237 ms 31824 KB Output is correct
10 Correct 28 ms 1756 KB Output is correct
11 Correct 428 ms 24048 KB Output is correct
12 Correct 434 ms 27048 KB Output is correct
13 Correct 325 ms 27756 KB Output is correct
14 Correct 28 ms 2500 KB Output is correct
15 Correct 362 ms 23532 KB Output is correct
16 Correct 377 ms 22268 KB Output is correct
17 Correct 390 ms 23148 KB Output is correct
18 Correct 415 ms 22888 KB Output is correct
19 Correct 461 ms 26604 KB Output is correct
20 Correct 449 ms 25784 KB Output is correct
21 Correct 263 ms 35288 KB Output is correct
22 Correct 273 ms 31552 KB Output is correct
23 Correct 342 ms 23072 KB Output is correct
24 Correct 328 ms 23052 KB Output is correct
25 Correct 477 ms 33852 KB Output is correct
26 Correct 375 ms 21484 KB Output is correct
27 Correct 340 ms 21376 KB Output is correct
28 Incorrect 27 ms 1604 KB Extra information in the output file
29 Halted 0 ms 0 KB -