oj.uz

Submission #846797

# Submission time Handle Problem Language Result Execution time Memory
846797 2023-09-08T12:53:12 Z MinaRagy06 Inside information (BOI21_servers) C++17
50 / 100
 294 ms 79312 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;

const int N = 120'005;
vector<array<int, 2>> adj[N];
//0: increasing, 1: decreasing, {ancestor, last weight}
array<int, 3> bl[2][18][N];
int st[N], en[N], curt;
void dfs(int i, int par, int part) {
    bl[0][0][i] = {par, part, part};
    bl[1][0][i] = {par, part, part};
    for (int j = 1; j < 18; j++) {
        bl[0][j][i] = bl[0][j - 1][i];
        auto [lst, lstt, mx] = bl[0][j][i];
        if (lstt <= bl[0][0][lst][1]) {
            bl[0][j][i] = bl[0][j - 1][lst];
            bl[0][j][i][2] = max(bl[0][j][i][2], mx);
        }
    }
    for (int j = 1; j < 18; j++) {
        bl[1][j][i] = bl[1][j - 1][i];
        auto [lst, lstt, mx] = bl[1][j][i];
        if (lstt >= bl[1][0][lst][1]) {
            bl[1][j][i] = bl[1][j - 1][lst];
            bl[1][j][i][2] = max(bl[1][j][i][2], mx);
        }
    }
    st[i] = curt++;
    for (auto [nxt, t] : adj[i]) {
        if (nxt == par) continue;
        dfs(nxt, i, t);
    }
    en[i] = curt;
}
bool lca(int l, int b) {
    if (st[l] <= st[b] && en[b] <= en[l]) {
        return 1;
    }
    return 0;
}
array<int, 2> check(int t, int a, int b) {
    int mx = -1e9, high = bl[t][17][a][0];
    if (!lca(high, b)) {
        return {int(1e9), 0};
    }
    if (a == high || lca(a, b)) {
        return {int(-1e9), (t == 1? 1 : -1) * int(1e9)};
    }
    for (int j = 17; j >= 0; j--) {
        if (!lca(bl[t][j][a][0], b) && !lca(bl[t][j][a][0], high)) {
            mx = max(mx, bl[t][j][a][2]);
            a = bl[t][j][a][0];
        }
    }
    return {max(mx, bl[t][0][a][2]), bl[t][0][a][1]};
}
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    q += n - 1;
    pair<char, vector<int>> v[q];
    for (int i = 0; i < q; i++) {
        cin >> v[i].first;
        if (v[i].first == 'S') {
            int a, b;
            cin >> a >> b;
            adj[a].push_back({b, i});
            adj[b].push_back({a, i});
        } else if (v[i].first == 'Q') {
            int a, b;
            cin >> a >> b;
            v[i].second = {a, b};
        } else {
            int a;
            cin >> a;
        }
    }
    dfs(1, 1, 0);
    for (int i = 0; i < q; i++) {
        if (v[i].first != 'Q') {
            continue;
        }
        int a = v[i].second[0], b = v[i].second[1];
        array<int, 2> l = check(1, a, b), r = check(0, b, a);
//        cout << l[0] << ' ' << l[1] << ' ' << r[0] << ' ' << r[1] << '\n';
        if (l[0] <= i && r[0] <= i && l[1] >= r[1]) {
            cout << "yes\n";
        } else {
            cout << "no\n";
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 62544 KB Output is correct
2 Correct 32 ms 62804 KB Output is correct
3 Correct 41 ms 62960 KB Output is correct
4 Correct 35 ms 62800 KB Output is correct
5 Correct 32 ms 63080 KB Output is correct
6 Correct 43 ms 62800 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 62544 KB Output is correct
2 Correct 32 ms 62804 KB Output is correct
3 Correct 41 ms 62960 KB Output is correct
4 Correct 35 ms 62800 KB Output is correct
5 Correct 32 ms 63080 KB Output is correct
6 Correct 43 ms 62800 KB Output is correct
7 Incorrect 30 ms 62288 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 31 ms 62552 KB Output is correct
2 Correct 233 ms 71364 KB Output is correct
3 Correct 211 ms 71108 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 62552 KB Output is correct
2 Correct 233 ms 71364 KB Output is correct
3 Correct 211 ms 71108 KB Output is correct
4 Incorrect 31 ms 62288 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 26 ms 62544 KB Output is correct
2 Correct 134 ms 75856 KB Output is correct
3 Correct 132 ms 75856 KB Output is correct
4 Correct 136 ms 78928 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62544 KB Output is correct
2 Correct 134 ms 75856 KB Output is correct
3 Correct 132 ms 75856 KB Output is correct
4 Correct 136 ms 78928 KB Output is correct
5 Incorrect 27 ms 63060 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 62556 KB Output is correct
2 Correct 117 ms 73040 KB Output is correct
3 Correct 145 ms 74576 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62556 KB Output is correct
2 Correct 117 ms 73040 KB Output is correct
3 Correct 145 ms 74576 KB Output is correct
4 Incorrect 29 ms 63052 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 26 ms 62544 KB Output is correct
2 Correct 148 ms 75856 KB Output is correct
3 Correct 152 ms 75856 KB Output is correct
4 Correct 128 ms 78636 KB Output is correct
5 Correct 30 ms 63312 KB Output is correct
6 Correct 138 ms 74324 KB Output is correct
7 Correct 172 ms 74576 KB Output is correct
8 Correct 173 ms 75600 KB Output is correct
9 Correct 233 ms 75344 KB Output is correct
10 Correct 257 ms 76772 KB Output is correct
11 Correct 277 ms 76076 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 62544 KB Output is correct
2 Correct 148 ms 75856 KB Output is correct
3 Correct 152 ms 75856 KB Output is correct
4 Correct 128 ms 78636 KB Output is correct
5 Correct 30 ms 63312 KB Output is correct
6 Correct 138 ms 74324 KB Output is correct
7 Correct 172 ms 74576 KB Output is correct
8 Correct 173 ms 75600 KB Output is correct
9 Correct 233 ms 75344 KB Output is correct
10 Correct 257 ms 76772 KB Output is correct
11 Correct 277 ms 76076 KB Output is correct
12 Incorrect 27 ms 63120 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 30 ms 62456 KB Output is correct
2 Correct 34 ms 62800 KB Output is correct
3 Correct 44 ms 62940 KB Output is correct
4 Correct 36 ms 62800 KB Output is correct
5 Correct 31 ms 63056 KB Output is correct
6 Correct 44 ms 62956 KB Output is correct
7 Correct 34 ms 62544 KB Output is correct
8 Correct 232 ms 73712 KB Output is correct
9 Correct 247 ms 74144 KB Output is correct
10 Correct 27 ms 63312 KB Output is correct
11 Correct 172 ms 79308 KB Output is correct
12 Correct 147 ms 79312 KB Output is correct
13 Correct 123 ms 79180 KB Output is correct
14 Correct 37 ms 63312 KB Output is correct
15 Correct 128 ms 74320 KB Output is correct
16 Correct 179 ms 74620 KB Output is correct
17 Correct 167 ms 75344 KB Output is correct
18 Correct 253 ms 75344 KB Output is correct
19 Correct 294 ms 76620 KB Output is correct
20 Correct 264 ms 76112 KB Output is correct
21 Correct 214 ms 74616 KB Output is correct
22 Correct 248 ms 74696 KB Output is correct
23 Correct 227 ms 74840 KB Output is correct
24 Correct 224 ms 74864 KB Output is correct
25 Correct 225 ms 75904 KB Output is correct
26 Correct 181 ms 74352 KB Output is correct
27 Correct 194 ms 74364 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 62456 KB Output is correct
2 Correct 34 ms 62800 KB Output is correct
3 Correct 44 ms 62940 KB Output is correct
4 Correct 36 ms 62800 KB Output is correct
5 Correct 31 ms 63056 KB Output is correct
6 Correct 44 ms 62956 KB Output is correct
7 Correct 34 ms 62544 KB Output is correct
8 Correct 232 ms 73712 KB Output is correct
9 Correct 247 ms 74144 KB Output is correct
10 Correct 27 ms 63312 KB Output is correct
11 Correct 172 ms 79308 KB Output is correct
12 Correct 147 ms 79312 KB Output is correct
13 Correct 123 ms 79180 KB Output is correct
14 Correct 37 ms 63312 KB Output is correct
15 Correct 128 ms 74320 KB Output is correct
16 Correct 179 ms 74620 KB Output is correct
17 Correct 167 ms 75344 KB Output is correct
18 Correct 253 ms 75344 KB Output is correct
19 Correct 294 ms 76620 KB Output is correct
20 Correct 264 ms 76112 KB Output is correct
21 Correct 214 ms 74616 KB Output is correct
22 Correct 248 ms 74696 KB Output is correct
23 Correct 227 ms 74840 KB Output is correct
24 Correct 224 ms 74864 KB Output is correct
25 Correct 225 ms 75904 KB Output is correct
26 Correct 181 ms 74352 KB Output is correct
27 Correct 194 ms 74364 KB Output is correct
28 Incorrect 44 ms 63076 KB Extra information in the output file
29 Halted 0 ms 0 KB -