oj.uz

Submission #572510

# Submission time Handle Problem Language Result Execution time Memory
572510 2022-06-04T14:45:16 Z Cyanmond Inside information (BOI21_servers) C++17
100 / 100
 956 ms 31548 KB 
#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

constexpr int inf = 1000000100;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)

#define ALL(x) (x).begin(), (x).end()

struct Query {
    bool type;
    int time;
    int v;
};

struct Edge {
    int to;
    int time;
};

struct BIT {
    int n;
    vector<int> data;

    BIT(int n_) : n(n_), data(n + 1) {}

    void add(int i, int v) {
        ++i;
        while (i <= n) {
            data[i] += v;
            i += i & -i;
        }
    }

    int fold(int r) {
        int ret = 0;
        while (r != 0) {
            ret += data[r];
            r -= r & -r;
        }
        return ret;
    }
};

int main() {
    int N, K;
    cin >> N >> K;
    vector<tuple<int, int, int>> Q(N + K - 1);
    vector<vector<Edge>> Tree(N);
    vector<int> ans(N + K - 1, -1);
    REP(i, N + K - 1) {
        auto &[c, a, b] = Q[i];
        char s;
        cin >> s >> a;
        --a;
        if (s == 'S') c = 0;
        if (s == 'Q') c = 1;
        if (s == 'C') c = 2;
        if (c != 2) {
            cin >> b;
            --b;
        }
        if (c == 0) {
            Tree[a].push_back({b, i});
            Tree[b].push_back({a, i});
        }
        if (c == 1 and a == b) ans[i] = 1;
        if (c == 2) ans[i] = 0;
    }

    REP(i, N) sort(ALL(Tree[i]), [](Edge a, Edge b) { return a.time < b.time; });

    vector<vector<Query>> qv(N);
    REP(i, N + K - 1) {
        const auto &[c, a, b] = Q[i];
        if (c == 0) continue;
        if (c == 1) qv[a].push_back({false, i, b});
        if (c == 2) qv[a].push_back({true, i, i});
    }

    vector<bool> is_valid(N, true);
    vector<int> subsize(N);
    auto centroid_decompose = [&](auto &&self, const int root, auto &solve1, auto &solve2) -> void {
        {
            auto dfs = [&](auto &&self, const int v, const int p) -> int {
                subsize[v] = 1;
                for (const auto &[to, dust] : Tree[v]) {
                    if (not is_valid[to]) continue;
                    if (to == p) continue;
                    subsize[v] += self(self, to, v);
                }
                return subsize[v];
            };
            dfs(dfs, root, -1);
        }
        const int count_v = subsize[root];
        int centroid = -1;
        {
            auto dfs = [&](auto &&self, const int v, const int p) -> void {
                bool is_centroid = true;
                for (const auto &[to, dust] : Tree[v]) {
                    if (not is_valid[to]) continue;
                    if (to == p) continue;
                    self(self, to, v);
                    if (subsize[to] > count_v / 2) is_centroid = false;
                }
                if (count_v - subsize[v] > count_v / 2) is_centroid = false;
                if (is_centroid) centroid = v;
            };
            dfs(dfs, root, -1);
        }

        solve1(centroid);
        solve2(centroid);

        {
            is_valid[centroid] = false;
            vector<vector<int>> vertices;
            for (const auto &[to, dust] : Tree[centroid]) {
                if (not is_valid[to]) continue;
                vertices.push_back({});
                auto dfs = [&](auto &&self, const int v, const int p) -> void {
                    vertices.back().push_back(v);
                    is_valid[v] = false;
                    for (const auto &[to, dust2] : Tree[v]) {
                        if (not is_valid[to]) continue;
                        if (to == p) continue;
                        self(self, to, v);
                    }
                };
                dfs(dfs, to, centroid);
            }
            for (const auto &ver : vertices) {
                for (const int ve : ver) is_valid[ve] = true;
                self(self, ver[0], solve1, solve2);
                for (const int ve : ver) is_valid[ve] = false;
            }
        }
    };

    vector<bool> is_inc(N), is_dec(N);
    vector<int> froot(N), pa_time(N);

    auto answer_query1 = [&](const int centroid) {
        {
            auto dfs = [&](auto &&self, const int v, const int p, const int last_time,
                           const int fr) -> void {
                froot[v] = fr;
                pa_time[v] = last_time;
                for (const auto &[to, time] : Tree[v]) {
                    if (not is_valid[to]) continue;
                    if (to == p) continue;
                    if (is_inc[v] and (last_time == -1 or time > last_time)) {
                        is_inc[to] = true;
                    } else {
                        is_inc[to] = false;
                    }
                    if (is_dec[v] and (last_time == -1 or time < last_time)) {
                        is_dec[to] = true;
                    } else {
                        is_dec[to] = false;
                    }
                    self(self, to, v, time, fr == -1 ? to : fr);
                }
            };
            is_inc[centroid] = is_dec[centroid] = true;
            dfs(dfs, centroid, -1, -1, -1);
        }
        {
            auto dfs = [&](auto &&self, const int v, const int p) -> void {
                for (const auto &[type, id, b] : qv[v]) {
                    if (not type) {
                        if (not is_valid[b]) continue;
                        if (froot[v] == froot[b]) continue;
                        if (ans[id] != -1) continue;
                        bool res = is_inc[v] and is_dec[b];
                        res &= (v == centroid ? pa_time[froot[b]] : pa_time[v]) <= id;
                        res &= (v == centroid ? inf : pa_time[froot[v]]) >=
                               (b == centroid ? -1 : pa_time[froot[b]]);
                        ans[id] = res;
                    }
                }
                for (const auto &[to, dust] : Tree[v]) {
                    if (not is_valid[to]) continue;
                    if (to == p) continue;
                    self(self, to, v);
                }
            };
            dfs(dfs, centroid, -1);
        }
    };

    auto answer_query2 = [&](const int centroid) {
        vector<int> press;
        {
            auto dfs = [&](auto &&self, const int v, const int p) -> void {
                for (const auto &[to, time] : Tree[v]) {
                    if (not is_valid[to]) continue;
                    if (to == p) continue;
                    press.push_back(time);
                    self(self, to, v);
                }
            };
            dfs(dfs, centroid, -1);
        }
        sort(ALL(press));
        press.erase(unique(ALL(press)), press.end());
        const int M = (int)size(press);
        BIT rmq(M);
        RVP(i, (int)size(Tree[centroid])) {
            const int r = Tree[centroid][i].to, rt = Tree[centroid][i].time;
            if (not is_valid[r]) continue;
            {
                auto dfs = [&](auto &&self, const int v, const int p) -> void {
                    for (const auto &[type, id, li] : qv[v]) {
                        if (not type) continue;
                        ans[id] += rmq.fold(lower_bound(ALL(press), li) - press.begin());
                        if (li > rt) ++ans[id];
                    }

                    for (const auto &[to, time] : Tree[v]) {
                        if (not is_valid[to]) continue;
                        if (to == p) continue;
                        if (not is_dec[to]) continue;
                        self(self, to, v);
                    }
                };
                dfs(dfs, r, centroid);
            }
            {
                auto dfs = [&](auto &&self, const int v, const int p, int last_time) -> void {
                    rmq.add(lower_bound(ALL(press), last_time) - press.begin(), 1);
                    for (const auto &[to, time] : Tree[v]) {
                        if (not is_valid[to]) continue;
                        if (to == p) continue;
                        if (not is_inc[to]) continue;
                        self(self, to, v, time);
                    }
                };
                dfs(dfs, r, centroid, rt);
            }
        }
        for (const auto &[type, id, li] : qv[centroid]) {
            if (not type) continue;
            ans[id] += rmq.fold(lower_bound(ALL(press), li) - press.begin());
        }
    };

    centroid_decompose(centroid_decompose, 0, answer_query1, answer_query2);
    REP(i, N + K - 1) {
        if (ans[i] == -1) continue;
        if (get<0>(Q[i]) == 1) {
            cout << (ans[i] ? "yes" : "no") << '\n';
        } else {
            cout << ans[i] + 1 << '\n';
        }
    }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5580 KB Output is correct
2 Correct 87 ms 6792 KB Output is correct
3 Correct 82 ms 6548 KB Output is correct
4 Correct 96 ms 6988 KB Output is correct
5 Correct 93 ms 6920 KB Output is correct
6 Correct 76 ms 6724 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5580 KB Output is correct
2 Correct 87 ms 6792 KB Output is correct
3 Correct 82 ms 6548 KB Output is correct
4 Correct 96 ms 6988 KB Output is correct
5 Correct 93 ms 6920 KB Output is correct
6 Correct 76 ms 6724 KB Output is correct
7 Correct 59 ms 5488 KB Output is correct
8 Correct 89 ms 6388 KB Output is correct
9 Correct 72 ms 6064 KB Output is correct
10 Correct 89 ms 6532 KB Output is correct
11 Correct 90 ms 6680 KB Output is correct
12 Correct 69 ms 6232 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5612 KB Output is correct
2 Correct 264 ms 27768 KB Output is correct
3 Correct 252 ms 27744 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5612 KB Output is correct
2 Correct 264 ms 27768 KB Output is correct
3 Correct 252 ms 27744 KB Output is correct
4 Correct 61 ms 5564 KB Output is correct
5 Correct 255 ms 27508 KB Output is correct
6 Correct 182 ms 25480 KB Output is correct
7 Correct 203 ms 25720 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5628 KB Output is correct
2 Correct 734 ms 29044 KB Output is correct
3 Correct 754 ms 29104 KB Output is correct
4 Correct 545 ms 28924 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5628 KB Output is correct
2 Correct 734 ms 29044 KB Output is correct
3 Correct 754 ms 29104 KB Output is correct
4 Correct 545 ms 28924 KB Output is correct
5 Correct 65 ms 5480 KB Output is correct
6 Correct 759 ms 28740 KB Output is correct
7 Correct 582 ms 28844 KB Output is correct
8 Correct 739 ms 28496 KB Output is correct
9 Correct 722 ms 28188 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5580 KB Output is correct
2 Correct 532 ms 23624 KB Output is correct
3 Correct 639 ms 23496 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5580 KB Output is correct
2 Correct 532 ms 23624 KB Output is correct
3 Correct 639 ms 23496 KB Output is correct
4 Correct 56 ms 5496 KB Output is correct
5 Correct 545 ms 23308 KB Output is correct
6 Correct 641 ms 23180 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5628 KB Output is correct
2 Correct 722 ms 29068 KB Output is correct
3 Correct 727 ms 29088 KB Output is correct
4 Correct 556 ms 29020 KB Output is correct
5 Correct 57 ms 5628 KB Output is correct
6 Correct 524 ms 23540 KB Output is correct
7 Correct 622 ms 23448 KB Output is correct
8 Correct 663 ms 24208 KB Output is correct
9 Correct 674 ms 24148 KB Output is correct
10 Correct 703 ms 26908 KB Output is correct
11 Correct 709 ms 27012 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5628 KB Output is correct
2 Correct 722 ms 29068 KB Output is correct
3 Correct 727 ms 29088 KB Output is correct
4 Correct 556 ms 29020 KB Output is correct
5 Correct 57 ms 5628 KB Output is correct
6 Correct 524 ms 23540 KB Output is correct
7 Correct 622 ms 23448 KB Output is correct
8 Correct 663 ms 24208 KB Output is correct
9 Correct 674 ms 24148 KB Output is correct
10 Correct 703 ms 26908 KB Output is correct
11 Correct 709 ms 27012 KB Output is correct
12 Correct 59 ms 5452 KB Output is correct
13 Correct 757 ms 28872 KB Output is correct
14 Correct 589 ms 28920 KB Output is correct
15 Correct 726 ms 28440 KB Output is correct
16 Correct 714 ms 28220 KB Output is correct
17 Correct 59 ms 5504 KB Output is correct
18 Correct 539 ms 23232 KB Output is correct
19 Correct 631 ms 23192 KB Output is correct
20 Correct 693 ms 23936 KB Output is correct
21 Correct 666 ms 24084 KB Output is correct
22 Correct 773 ms 26072 KB Output is correct
23 Correct 930 ms 26544 KB Output is correct
24 Correct 886 ms 26772 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5576 KB Output is correct
2 Correct 93 ms 6732 KB Output is correct
3 Correct 80 ms 6596 KB Output is correct
4 Correct 91 ms 6836 KB Output is correct
5 Correct 91 ms 6960 KB Output is correct
6 Correct 79 ms 6764 KB Output is correct
7 Correct 59 ms 5708 KB Output is correct
8 Correct 268 ms 27968 KB Output is correct
9 Correct 273 ms 27820 KB Output is correct
10 Correct 59 ms 5628 KB Output is correct
11 Correct 756 ms 29044 KB Output is correct
12 Correct 750 ms 29056 KB Output is correct
13 Correct 561 ms 28908 KB Output is correct
14 Correct 58 ms 5580 KB Output is correct
15 Correct 526 ms 23572 KB Output is correct
16 Correct 687 ms 23408 KB Output is correct
17 Correct 670 ms 24260 KB Output is correct
18 Correct 713 ms 24136 KB Output is correct
19 Correct 722 ms 26884 KB Output is correct
20 Correct 762 ms 26828 KB Output is correct
21 Correct 331 ms 28568 KB Output is correct
22 Correct 308 ms 27092 KB Output is correct
23 Correct 444 ms 23976 KB Output is correct
24 Correct 439 ms 23800 KB Output is correct
25 Correct 690 ms 31548 KB Output is correct
26 Correct 626 ms 22680 KB Output is correct
27 Correct 595 ms 22804 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5576 KB Output is correct
2 Correct 93 ms 6732 KB Output is correct
3 Correct 80 ms 6596 KB Output is correct
4 Correct 91 ms 6836 KB Output is correct
5 Correct 91 ms 6960 KB Output is correct
6 Correct 79 ms 6764 KB Output is correct
7 Correct 59 ms 5708 KB Output is correct
8 Correct 268 ms 27968 KB Output is correct
9 Correct 273 ms 27820 KB Output is correct
10 Correct 59 ms 5628 KB Output is correct
11 Correct 756 ms 29044 KB Output is correct
12 Correct 750 ms 29056 KB Output is correct
13 Correct 561 ms 28908 KB Output is correct
14 Correct 58 ms 5580 KB Output is correct
15 Correct 526 ms 23572 KB Output is correct
16 Correct 687 ms 23408 KB Output is correct
17 Correct 670 ms 24260 KB Output is correct
18 Correct 713 ms 24136 KB Output is correct
19 Correct 722 ms 26884 KB Output is correct
20 Correct 762 ms 26828 KB Output is correct
21 Correct 331 ms 28568 KB Output is correct
22 Correct 308 ms 27092 KB Output is correct
23 Correct 444 ms 23976 KB Output is correct
24 Correct 439 ms 23800 KB Output is correct
25 Correct 690 ms 31548 KB Output is correct
26 Correct 626 ms 22680 KB Output is correct
27 Correct 595 ms 22804 KB Output is correct
28 Correct 56 ms 5492 KB Output is correct
29 Correct 89 ms 6432 KB Output is correct
30 Correct 71 ms 6044 KB Output is correct
31 Correct 94 ms 6572 KB Output is correct
32 Correct 88 ms 6672 KB Output is correct
33 Correct 68 ms 6260 KB Output is correct
34 Correct 57 ms 5492 KB Output is correct
35 Correct 248 ms 27572 KB Output is correct
36 Correct 179 ms 25400 KB Output is correct
37 Correct 198 ms 25728 KB Output is correct
38 Correct 60 ms 5452 KB Output is correct
39 Correct 762 ms 28632 KB Output is correct
40 Correct 580 ms 28792 KB Output is correct
41 Correct 715 ms 28448 KB Output is correct
42 Correct 710 ms 28204 KB Output is correct
43 Correct 57 ms 5452 KB Output is correct
44 Correct 557 ms 23376 KB Output is correct
45 Correct 626 ms 23208 KB Output is correct
46 Correct 669 ms 23892 KB Output is correct
47 Correct 681 ms 24084 KB Output is correct
48 Correct 759 ms 26016 KB Output is correct
49 Correct 943 ms 26424 KB Output is correct
50 Correct 956 ms 26852 KB Output is correct
51 Correct 264 ms 26960 KB Output is correct
52 Correct 231 ms 26724 KB Output is correct
53 Correct 229 ms 26392 KB Output is correct
54 Correct 247 ms 26644 KB Output is correct
55 Correct 243 ms 26592 KB Output is correct
56 Correct 442 ms 22784 KB Output is correct
57 Correct 649 ms 29928 KB Output is correct
58 Correct 703 ms 22456 KB Output is correct
59 Correct 598 ms 23132 KB Output is correct