oj.uz

Submission #846793

# Submission time Handle Problem Language Result Execution time Memory
846793 2023-09-08T12:40:24 Z MinaRagy06 Inside information (BOI21_servers) C++17
2.5 / 100
 213 ms 73980 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) {
        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);
        if (l[0] <= i && r[0] <= i && l[1] >= r[1]) {
            cout << "yes\n";
        } else {
            cout << "no\n";
        }
    }
    return 0;
}

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 62544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 62544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62548 KB Output is correct
2 Correct 213 ms 73928 KB Output is correct
3 Correct 211 ms 73980 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62548 KB Output is correct
2 Correct 213 ms 73928 KB Output is correct
3 Correct 211 ms 73980 KB Output is correct
4 Incorrect 31 ms 63056 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 62468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 62468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 62476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 62476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 62544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 62544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 62544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 62544 KB Output isn't correct
2 Halted 0 ms 0 KB -