oj.uz

Submission #413510

# Submission time Handle Problem Language Result Execution time Memory
413510 2021-05-28T19:43:07 Z Tc14 Inside information (BOI21_servers) C++17
55 / 100
 737 ms 73848 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;
const int L = 20;

struct path {
    bool asc, dec;
    int min, max;
};

path combine(path a, path b) {

    bool asc, dec;

    if (a.min == -1) return b;
    if (b.min == -1) return a;

    asc = a.asc && b.asc && a.max < b.min;

    dec = a.dec && b.dec && a.min > b.max;

    return {asc, dec, min(a.min, b.min), max(a.max, b.max)};
}

ve<int> D;
ve<ve<int>> A;
ve<ve<pii>> G;
ve<ve<path>> X;

void f(int u, int p, int s, int d) {

    int a = p;
    path x = {true, true, s, s};
    for (int i = 0; i < L; i++) {

        A[u][i] = a;
        X[u][i] = x;

        if (a != -1) {
            x = combine(x, X[a][i]);
            a = A[a][i];
        }
    }
    D[u] = d;

    for (pii e : G[u]) {
        int v, t;
        tie(v, t) = e;
        if (v != p) f(v, u, t, d + 1);
    }
}

int lca(int a, int b) {

    bool swp = false;
    if (D[a] < D[b]) {
        swap(a, b);
        swp = true;
    }

    path xa = {true, true, -1, -1};
    path xb = {true, true, -1, -1};

    for (int i = L - 1; i >= 0; i--) {
        if (D[a] - (1 << i) >= D[b]) {
            xa = combine(xa, X[a][i]);
            a = A[a][i];
        }
    }

    if (a != b) {

        for (int i = L - 1; i >= 0; i--) {

            if (A[a][i] != A[b][i]) {

                xa = combine(xa, X[a][i]);
                a = A[a][i];

                xb = combine(xb, X[b][i]);
                b = A[b][i];
            }
        }

        xa = combine(xa, X[a][0]);
        xb = combine(xb, X[b][0]);
    }

    if (swp) swap(xa, xb);

    swap(xb.asc, xb.dec);
    path x = combine(xa, xb);

    if (x.asc) return x.max;
    else return INF;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k, a, b, d, t;
    ve<tuple<int, int, int, int>> Q;
    ve<int> Z, Left, Right;

    cin >> n >> k;

    D = ve<int>(n);
    A = ve<ve<int>>(n, ve<int>(L));
    G = ve<ve<pii>>(n);
    X = ve<ve<path>>(n, ve<path>(L));

    Z = ve<int>(n - 1);
    Left = ve<int>(n);
    Right = ve<int>(n);

    t = 0;
    for (int i = 0; i < n + k - 1; i++) {

        char c;
        cin >> c;

        if (c == 'S') {
            cin >> a >> b;
            a--;
            b--;
            t++;
            G[a].push_back({b, t});
            G[b].push_back({a, t});
            Z[min(a, b)] = t;
        }
        else if (c == 'Q') {
            cin >> a >> d;
            a--;
            d--;
            Q.push_back({1, a, d, t});
        }
        else {
            cin >> d;
            d--;
            Q.push_back({2, d, t, 0});
        }
    }

    f(0, -1, -1, 0);

    int prev = INF;
    int cnt = 0;
    Left[0] = 0;
    for (int i = 0; i < n - 1; i++) {
        if (Z[i] < prev) cnt++;
        else cnt = 1;
        Left[i + 1] = cnt;
        prev = Z[i];
    }

    prev = INF;
    cnt = 0;
    Right[n - 1] = 0;
    for (int i = n - 2; i >= 0; i--) {
        if (Z[i] < prev) cnt++;
        else cnt = 1;
        Right[i] = cnt;
        prev = Z[i];
    }

    for (int i = 0; i < k; i++) {
        if (get<0>(Q[i]) == 1) {
            tie(ignore, a, d, t) = Q[i];
            int r = lca(d, a);
            if (r <= t) cout << "yes" << endl;
            else cout << "no" << endl;
        }
        else {

            int ans = 1;
            tie(ignore, d, t, ignore) = Q[i];

            auto y = Z.begin() + d;
            auto x = y - Left[d];
            auto it = lower_bound(x, y, t, greater<int>());
            ans += (int)distance(it, y);

            x = Z.begin() + d;
            y = x + Right[d];
            it = upper_bound(x, y, t);
            ans += (int)distance(x, it);

            cout << ans << endl;
        }
    }

    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 229 ms 2744 KB Output is correct
2 Correct 273 ms 4488 KB Output is correct
3 Correct 250 ms 4748 KB Output is correct
4 Correct 283 ms 4596 KB Output is correct
5 Correct 260 ms 4976 KB Output is correct
6 Correct 238 ms 4532 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 229 ms 2744 KB Output is correct
2 Correct 273 ms 4488 KB Output is correct
3 Correct 250 ms 4748 KB Output is correct
4 Correct 283 ms 4596 KB Output is correct
5 Correct 260 ms 4976 KB Output is correct
6 Correct 238 ms 4532 KB Output is correct
7 Incorrect 231 ms 2728 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 227 ms 2732 KB Output is correct
2 Correct 480 ms 59204 KB Output is correct
3 Correct 426 ms 59060 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 227 ms 2732 KB Output is correct
2 Correct 480 ms 59204 KB Output is correct
3 Correct 426 ms 59060 KB Output is correct
4 Incorrect 225 ms 2744 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 228 ms 2728 KB Output is correct
2 Correct 452 ms 71320 KB Output is correct
3 Correct 467 ms 71304 KB Output is correct
4 Correct 591 ms 71348 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 2728 KB Output is correct
2 Correct 452 ms 71320 KB Output is correct
3 Correct 467 ms 71304 KB Output is correct
4 Correct 591 ms 71348 KB Output is correct
5 Correct 218 ms 2772 KB Output is correct
6 Correct 452 ms 73692 KB Output is correct
7 Correct 488 ms 73784 KB Output is correct
8 Correct 420 ms 73620 KB Output is correct
9 Correct 423 ms 73720 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 2744 KB Output is correct
2 Correct 440 ms 59088 KB Output is correct
3 Correct 434 ms 59640 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 2744 KB Output is correct
2 Correct 440 ms 59088 KB Output is correct
3 Correct 434 ms 59640 KB Output is correct
4 Incorrect 232 ms 2708 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 267 ms 2772 KB Output is correct
2 Correct 493 ms 71312 KB Output is correct
3 Correct 462 ms 71336 KB Output is correct
4 Correct 548 ms 71268 KB Output is correct
5 Correct 240 ms 2672 KB Output is correct
6 Correct 433 ms 59172 KB Output is correct
7 Correct 440 ms 59636 KB Output is correct
8 Correct 552 ms 60040 KB Output is correct
9 Correct 454 ms 60104 KB Output is correct
10 Correct 560 ms 65840 KB Output is correct
11 Correct 737 ms 64964 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 267 ms 2772 KB Output is correct
2 Correct 493 ms 71312 KB Output is correct
3 Correct 462 ms 71336 KB Output is correct
4 Correct 548 ms 71268 KB Output is correct
5 Correct 240 ms 2672 KB Output is correct
6 Correct 433 ms 59172 KB Output is correct
7 Correct 440 ms 59636 KB Output is correct
8 Correct 552 ms 60040 KB Output is correct
9 Correct 454 ms 60104 KB Output is correct
10 Correct 560 ms 65840 KB Output is correct
11 Correct 737 ms 64964 KB Output is correct
12 Correct 243 ms 2728 KB Output is correct
13 Correct 443 ms 73784 KB Output is correct
14 Correct 482 ms 73848 KB Output is correct
15 Correct 435 ms 73572 KB Output is correct
16 Correct 470 ms 73612 KB Output is correct
17 Incorrect 256 ms 2672 KB Extra information in the output file
18 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 245 ms 2692 KB Output is correct
2 Correct 295 ms 4456 KB Output is correct
3 Correct 264 ms 4516 KB Output is correct
4 Correct 296 ms 4604 KB Output is correct
5 Correct 275 ms 4984 KB Output is correct
6 Correct 253 ms 4552 KB Output is correct
7 Correct 233 ms 2712 KB Output is correct
8 Correct 454 ms 59148 KB Output is correct
9 Correct 458 ms 59092 KB Output is correct
10 Correct 231 ms 2688 KB Output is correct
11 Correct 470 ms 71412 KB Output is correct
12 Correct 476 ms 71360 KB Output is correct
13 Correct 565 ms 71332 KB Output is correct
14 Correct 265 ms 2648 KB Output is correct
15 Correct 443 ms 59108 KB Output is correct
16 Correct 451 ms 59604 KB Output is correct
17 Correct 615 ms 60012 KB Output is correct
18 Correct 485 ms 59996 KB Output is correct
19 Correct 608 ms 65880 KB Output is correct
20 Correct 719 ms 64900 KB Output is correct
21 Correct 452 ms 59052 KB Output is correct
22 Correct 497 ms 59200 KB Output is correct
23 Correct 486 ms 59540 KB Output is correct
24 Correct 485 ms 59540 KB Output is correct
25 Correct 513 ms 62340 KB Output is correct
26 Correct 411 ms 58900 KB Output is correct
27 Correct 406 ms 59068 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 245 ms 2692 KB Output is correct
2 Correct 295 ms 4456 KB Output is correct
3 Correct 264 ms 4516 KB Output is correct
4 Correct 296 ms 4604 KB Output is correct
5 Correct 275 ms 4984 KB Output is correct
6 Correct 253 ms 4552 KB Output is correct
7 Correct 233 ms 2712 KB Output is correct
8 Correct 454 ms 59148 KB Output is correct
9 Correct 458 ms 59092 KB Output is correct
10 Correct 231 ms 2688 KB Output is correct
11 Correct 470 ms 71412 KB Output is correct
12 Correct 476 ms 71360 KB Output is correct
13 Correct 565 ms 71332 KB Output is correct
14 Correct 265 ms 2648 KB Output is correct
15 Correct 443 ms 59108 KB Output is correct
16 Correct 451 ms 59604 KB Output is correct
17 Correct 615 ms 60012 KB Output is correct
18 Correct 485 ms 59996 KB Output is correct
19 Correct 608 ms 65880 KB Output is correct
20 Correct 719 ms 64900 KB Output is correct
21 Correct 452 ms 59052 KB Output is correct
22 Correct 497 ms 59200 KB Output is correct
23 Correct 486 ms 59540 KB Output is correct
24 Correct 485 ms 59540 KB Output is correct
25 Correct 513 ms 62340 KB Output is correct
26 Correct 411 ms 58900 KB Output is correct
27 Correct 406 ms 59068 KB Output is correct
28 Incorrect 238 ms 2672 KB Extra information in the output file
29 Halted 0 ms 0 KB -