oj.uz

Submission #572440

# Submission time Handle Problem Language Result Execution time Memory
572440 2022-06-04T11:35:40 Z Cyanmond Inside information (BOI21_servers) C++17
50 / 100
 674 ms 31552 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;
};

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;
    }

    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, 0});
    }

    vector<bool> is_valid(N, true);
    vector<int> subsize(N);
    auto centroid_decompose = [&](auto &&self, const int root, auto &solve) -> 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);
        }

        solve(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], solve);
                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_query = [&](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);
        }
    };

    centroid_decompose(centroid_decompose, 0, answer_query);
    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] << '\n';
        }
    }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 66 ms 5172 KB Output is correct
2 Correct 86 ms 6720 KB Output is correct
3 Correct 79 ms 6556 KB Output is correct
4 Correct 88 ms 6968 KB Output is correct
5 Correct 88 ms 6920 KB Output is correct
6 Correct 82 ms 6712 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 66 ms 5172 KB Output is correct
2 Correct 86 ms 6720 KB Output is correct
3 Correct 79 ms 6556 KB Output is correct
4 Correct 88 ms 6968 KB Output is correct
5 Correct 88 ms 6920 KB Output is correct
6 Correct 82 ms 6712 KB Output is correct
7 Incorrect 61 ms 5480 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 58 ms 5080 KB Output is correct
2 Correct 257 ms 25520 KB Output is correct
3 Correct 240 ms 25716 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5080 KB Output is correct
2 Correct 257 ms 25520 KB Output is correct
3 Correct 240 ms 25716 KB Output is correct
4 Incorrect 57 ms 4948 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 65 ms 5040 KB Output is correct
2 Correct 626 ms 28536 KB Output is correct
3 Correct 614 ms 28484 KB Output is correct
4 Correct 396 ms 28328 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5040 KB Output is correct
2 Correct 626 ms 28536 KB Output is correct
3 Correct 614 ms 28484 KB Output is correct
4 Correct 396 ms 28328 KB Output is correct
5 Incorrect 70 ms 5452 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 62 ms 5044 KB Output is correct
2 Correct 394 ms 20012 KB Output is correct
3 Correct 588 ms 20084 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 5044 KB Output is correct
2 Correct 394 ms 20012 KB Output is correct
3 Correct 588 ms 20084 KB Output is correct
4 Incorrect 59 ms 4972 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 62 ms 5036 KB Output is correct
2 Correct 588 ms 28432 KB Output is correct
3 Correct 674 ms 28484 KB Output is correct
4 Correct 386 ms 28396 KB Output is correct
5 Correct 62 ms 5632 KB Output is correct
6 Correct 388 ms 22568 KB Output is correct
7 Correct 528 ms 22604 KB Output is correct
8 Correct 555 ms 23556 KB Output is correct
9 Correct 569 ms 23284 KB Output is correct
10 Correct 554 ms 26180 KB Output is correct
11 Correct 591 ms 26056 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 5036 KB Output is correct
2 Correct 588 ms 28432 KB Output is correct
3 Correct 674 ms 28484 KB Output is correct
4 Correct 386 ms 28396 KB Output is correct
5 Correct 62 ms 5632 KB Output is correct
6 Correct 388 ms 22568 KB Output is correct
7 Correct 528 ms 22604 KB Output is correct
8 Correct 555 ms 23556 KB Output is correct
9 Correct 569 ms 23284 KB Output is correct
10 Correct 554 ms 26180 KB Output is correct
11 Correct 591 ms 26056 KB Output is correct
12 Incorrect 59 ms 5484 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 65 ms 5068 KB Output is correct
2 Correct 91 ms 6712 KB Output is correct
3 Correct 76 ms 6604 KB Output is correct
4 Correct 94 ms 6900 KB Output is correct
5 Correct 93 ms 6984 KB Output is correct
6 Correct 76 ms 6728 KB Output is correct
7 Correct 62 ms 5616 KB Output is correct
8 Correct 270 ms 27776 KB Output is correct
9 Correct 228 ms 27764 KB Output is correct
10 Correct 57 ms 5632 KB Output is correct
11 Correct 594 ms 28424 KB Output is correct
12 Correct 642 ms 28548 KB Output is correct
13 Correct 394 ms 28288 KB Output is correct
14 Correct 64 ms 5628 KB Output is correct
15 Correct 431 ms 22584 KB Output is correct
16 Correct 515 ms 22576 KB Output is correct
17 Correct 557 ms 23652 KB Output is correct
18 Correct 562 ms 23408 KB Output is correct
19 Correct 556 ms 26272 KB Output is correct
20 Correct 574 ms 26132 KB Output is correct
21 Correct 260 ms 28600 KB Output is correct
22 Correct 273 ms 27144 KB Output is correct
23 Correct 395 ms 23240 KB Output is correct
24 Correct 389 ms 23376 KB Output is correct
25 Correct 622 ms 31552 KB Output is correct
26 Correct 538 ms 22176 KB Output is correct
27 Correct 516 ms 22344 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5068 KB Output is correct
2 Correct 91 ms 6712 KB Output is correct
3 Correct 76 ms 6604 KB Output is correct
4 Correct 94 ms 6900 KB Output is correct
5 Correct 93 ms 6984 KB Output is correct
6 Correct 76 ms 6728 KB Output is correct
7 Correct 62 ms 5616 KB Output is correct
8 Correct 270 ms 27776 KB Output is correct
9 Correct 228 ms 27764 KB Output is correct
10 Correct 57 ms 5632 KB Output is correct
11 Correct 594 ms 28424 KB Output is correct
12 Correct 642 ms 28548 KB Output is correct
13 Correct 394 ms 28288 KB Output is correct
14 Correct 64 ms 5628 KB Output is correct
15 Correct 431 ms 22584 KB Output is correct
16 Correct 515 ms 22576 KB Output is correct
17 Correct 557 ms 23652 KB Output is correct
18 Correct 562 ms 23408 KB Output is correct
19 Correct 556 ms 26272 KB Output is correct
20 Correct 574 ms 26132 KB Output is correct
21 Correct 260 ms 28600 KB Output is correct
22 Correct 273 ms 27144 KB Output is correct
23 Correct 395 ms 23240 KB Output is correct
24 Correct 389 ms 23376 KB Output is correct
25 Correct 622 ms 31552 KB Output is correct
26 Correct 538 ms 22176 KB Output is correct
27 Correct 516 ms 22344 KB Output is correct
28 Incorrect 72 ms 5420 KB Extra information in the output file
29 Halted 0 ms 0 KB -