oj.uz

Submission #413479

# Submission time Handle Problem Language Result Execution time Memory
413479 2021-05-28T19:13:26 Z Tc14 Inside information (BOI21_servers) C++17
50 / 100
 705 ms 74648 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];

            if (Left[d] != 0) {

                auto y = Z.begin() + d;
                auto x = y - Left[d];

                auto it = lower_bound(x, y, t, greater<int>());
                int inc = (int)distance(it, y);

                ans += inc;
            }

            if (Right[d] != 0) {
                auto x = Z.begin() + d;
                auto y = x + Right[d];

                auto it = lower_bound(x, y, t);
                int inc = (int)distance(x, it);

                ans += inc;
            }

            cout << ans << endl;
        }
    }

    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 231 ms 2656 KB Output is correct
2 Correct 286 ms 5800 KB Output is correct
3 Correct 242 ms 6012 KB Output is correct
4 Correct 283 ms 5904 KB Output is correct
5 Correct 257 ms 6308 KB Output is correct
6 Correct 240 ms 5856 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 231 ms 2656 KB Output is correct
2 Correct 286 ms 5800 KB Output is correct
3 Correct 242 ms 6012 KB Output is correct
4 Correct 283 ms 5904 KB Output is correct
5 Correct 257 ms 6308 KB Output is correct
6 Correct 240 ms 5856 KB Output is correct
7 Incorrect 230 ms 2792 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 2692 KB Output is correct
2 Correct 437 ms 61800 KB Output is correct
3 Correct 461 ms 61948 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 227 ms 2692 KB Output is correct
2 Correct 437 ms 61800 KB Output is correct
3 Correct 461 ms 61948 KB Output is correct
4 Incorrect 231 ms 2848 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 252 ms 2604 KB Output is correct
2 Correct 454 ms 74504 KB Output is correct
3 Correct 462 ms 74508 KB Output is correct
4 Correct 546 ms 74400 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 2604 KB Output is correct
2 Correct 454 ms 74504 KB Output is correct
3 Correct 462 ms 74508 KB Output is correct
4 Correct 546 ms 74400 KB Output is correct
5 Incorrect 219 ms 2800 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 229 ms 2608 KB Output is correct
2 Correct 453 ms 62324 KB Output is correct
3 Correct 415 ms 62732 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 2608 KB Output is correct
2 Correct 453 ms 62324 KB Output is correct
3 Correct 415 ms 62732 KB Output is correct
4 Incorrect 234 ms 2716 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 222 ms 2884 KB Output is correct
2 Correct 464 ms 74648 KB Output is correct
3 Correct 474 ms 74544 KB Output is correct
4 Correct 559 ms 74396 KB Output is correct
5 Correct 230 ms 3596 KB Output is correct
6 Correct 440 ms 62236 KB Output is correct
7 Correct 490 ms 62764 KB Output is correct
8 Correct 579 ms 63224 KB Output is correct
9 Correct 459 ms 63160 KB Output is correct
10 Correct 553 ms 69016 KB Output is correct
11 Correct 705 ms 68108 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 222 ms 2884 KB Output is correct
2 Correct 464 ms 74648 KB Output is correct
3 Correct 474 ms 74544 KB Output is correct
4 Correct 559 ms 74396 KB Output is correct
5 Correct 230 ms 3596 KB Output is correct
6 Correct 440 ms 62236 KB Output is correct
7 Correct 490 ms 62764 KB Output is correct
8 Correct 579 ms 63224 KB Output is correct
9 Correct 459 ms 63160 KB Output is correct
10 Correct 553 ms 69016 KB Output is correct
11 Correct 705 ms 68108 KB Output is correct
12 Incorrect 241 ms 2796 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 255 ms 2684 KB Output is correct
2 Correct 294 ms 5736 KB Output is correct
3 Correct 242 ms 5900 KB Output is correct
4 Correct 285 ms 5884 KB Output is correct
5 Correct 265 ms 6348 KB Output is correct
6 Correct 263 ms 5808 KB Output is correct
7 Correct 221 ms 3712 KB Output is correct
8 Correct 434 ms 61736 KB Output is correct
9 Correct 480 ms 61828 KB Output is correct
10 Correct 230 ms 3636 KB Output is correct
11 Correct 471 ms 74484 KB Output is correct
12 Correct 531 ms 74508 KB Output is correct
13 Correct 545 ms 74632 KB Output is correct
14 Correct 230 ms 3508 KB Output is correct
15 Correct 453 ms 62380 KB Output is correct
16 Correct 408 ms 62768 KB Output is correct
17 Correct 594 ms 63236 KB Output is correct
18 Correct 465 ms 63228 KB Output is correct
19 Correct 532 ms 69068 KB Output is correct
20 Correct 701 ms 68120 KB Output is correct
21 Correct 440 ms 62352 KB Output is correct
22 Correct 446 ms 62376 KB Output is correct
23 Correct 450 ms 62552 KB Output is correct
24 Correct 466 ms 62764 KB Output is correct
25 Correct 515 ms 65496 KB Output is correct
26 Correct 498 ms 62164 KB Output is correct
27 Correct 401 ms 62248 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 255 ms 2684 KB Output is correct
2 Correct 294 ms 5736 KB Output is correct
3 Correct 242 ms 5900 KB Output is correct
4 Correct 285 ms 5884 KB Output is correct
5 Correct 265 ms 6348 KB Output is correct
6 Correct 263 ms 5808 KB Output is correct
7 Correct 221 ms 3712 KB Output is correct
8 Correct 434 ms 61736 KB Output is correct
9 Correct 480 ms 61828 KB Output is correct
10 Correct 230 ms 3636 KB Output is correct
11 Correct 471 ms 74484 KB Output is correct
12 Correct 531 ms 74508 KB Output is correct
13 Correct 545 ms 74632 KB Output is correct
14 Correct 230 ms 3508 KB Output is correct
15 Correct 453 ms 62380 KB Output is correct
16 Correct 408 ms 62768 KB Output is correct
17 Correct 594 ms 63236 KB Output is correct
18 Correct 465 ms 63228 KB Output is correct
19 Correct 532 ms 69068 KB Output is correct
20 Correct 701 ms 68120 KB Output is correct
21 Correct 440 ms 62352 KB Output is correct
22 Correct 446 ms 62376 KB Output is correct
23 Correct 450 ms 62552 KB Output is correct
24 Correct 466 ms 62764 KB Output is correct
25 Correct 515 ms 65496 KB Output is correct
26 Correct 498 ms 62164 KB Output is correct
27 Correct 401 ms 62248 KB Output is correct
28 Incorrect 240 ms 2772 KB Extra information in the output file
29 Halted 0 ms 0 KB -