oj.uz

Submission #413504

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

/*
    cout << " ";
    for (int i = 0; i < n - 1; i++) cout << Z[i] << " ";
    cout << endl;

    for (int i = 0; i < n; i++) cout << Left[i] << " ";
    cout << endl;

    for (int i = 0; i < n; i++) cout << Right[i] << " ";
    cout << endl;
*/

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

            //cout << d << " " << t << endl;

            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;

                //cout << inc << "  " << distance(Z.begin(), it) << endl;
            }

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

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

                ans += inc;

                //cout << inc << "  " << distance(Z.begin(), it) << endl;
            }

            cout << ans << endl;
        }
    }

    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 267 ms 3400 KB Output is correct
2 Correct 300 ms 5756 KB Output is correct
3 Correct 239 ms 5892 KB Output is correct
4 Correct 289 ms 5884 KB Output is correct
5 Correct 263 ms 6392 KB Output is correct
6 Correct 256 ms 5820 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 267 ms 3400 KB Output is correct
2 Correct 300 ms 5756 KB Output is correct
3 Correct 239 ms 5892 KB Output is correct
4 Correct 289 ms 5884 KB Output is correct
5 Correct 263 ms 6392 KB Output is correct
6 Correct 256 ms 5820 KB Output is correct
7 Incorrect 235 ms 2796 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 222 ms 3384 KB Output is correct
2 Correct 430 ms 61076 KB Output is correct
3 Correct 425 ms 61144 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 222 ms 3384 KB Output is correct
2 Correct 430 ms 61076 KB Output is correct
3 Correct 425 ms 61144 KB Output is correct
4 Incorrect 221 ms 2888 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 224 ms 3344 KB Output is correct
2 Correct 457 ms 73496 KB Output is correct
3 Correct 443 ms 73360 KB Output is correct
4 Correct 540 ms 73556 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 3344 KB Output is correct
2 Correct 457 ms 73496 KB Output is correct
3 Correct 443 ms 73360 KB Output is correct
4 Correct 540 ms 73556 KB Output is correct
5 Correct 221 ms 2896 KB Output is correct
6 Correct 506 ms 74044 KB Output is correct
7 Correct 521 ms 74212 KB Output is correct
8 Correct 409 ms 73668 KB Output is correct
9 Correct 410 ms 73816 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 3280 KB Output is correct
2 Correct 448 ms 61088 KB Output is correct
3 Correct 411 ms 61688 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 3280 KB Output is correct
2 Correct 448 ms 61088 KB Output is correct
3 Correct 411 ms 61688 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 270 ms 3356 KB Output is correct
2 Correct 452 ms 73396 KB Output is correct
3 Correct 464 ms 73412 KB Output is correct
4 Correct 592 ms 73332 KB Output is correct
5 Correct 231 ms 3520 KB Output is correct
6 Correct 435 ms 61084 KB Output is correct
7 Correct 405 ms 61624 KB Output is correct
8 Correct 541 ms 61984 KB Output is correct
9 Correct 461 ms 62004 KB Output is correct
10 Correct 527 ms 67920 KB Output is correct
11 Correct 670 ms 67092 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 270 ms 3356 KB Output is correct
2 Correct 452 ms 73396 KB Output is correct
3 Correct 464 ms 73412 KB Output is correct
4 Correct 592 ms 73332 KB Output is correct
5 Correct 231 ms 3520 KB Output is correct
6 Correct 435 ms 61084 KB Output is correct
7 Correct 405 ms 61624 KB Output is correct
8 Correct 541 ms 61984 KB Output is correct
9 Correct 461 ms 62004 KB Output is correct
10 Correct 527 ms 67920 KB Output is correct
11 Correct 670 ms 67092 KB Output is correct
12 Correct 225 ms 2788 KB Output is correct
13 Correct 432 ms 74036 KB Output is correct
14 Correct 486 ms 74232 KB Output is correct
15 Correct 439 ms 73684 KB Output is correct
16 Correct 447 ms 73676 KB Output is correct
17 Incorrect 229 ms 3640 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 234 ms 3380 KB Output is correct
2 Correct 262 ms 5812 KB Output is correct
3 Correct 249 ms 5976 KB Output is correct
4 Correct 294 ms 5936 KB Output is correct
5 Correct 273 ms 6348 KB Output is correct
6 Correct 242 ms 5772 KB Output is correct
7 Correct 225 ms 3656 KB Output is correct
8 Correct 417 ms 61184 KB Output is correct
9 Correct 470 ms 60836 KB Output is correct
10 Correct 223 ms 3512 KB Output is correct
11 Correct 461 ms 73036 KB Output is correct
12 Correct 472 ms 72968 KB Output is correct
13 Correct 520 ms 72964 KB Output is correct
14 Correct 235 ms 3768 KB Output is correct
15 Correct 437 ms 60740 KB Output is correct
16 Correct 416 ms 61432 KB Output is correct
17 Correct 547 ms 61700 KB Output is correct
18 Correct 460 ms 61692 KB Output is correct
19 Correct 535 ms 67492 KB Output is correct
20 Correct 705 ms 66504 KB Output is correct
21 Correct 436 ms 60736 KB Output is correct
22 Correct 450 ms 60832 KB Output is correct
23 Correct 453 ms 61196 KB Output is correct
24 Correct 490 ms 61388 KB Output is correct
25 Correct 480 ms 64088 KB Output is correct
26 Correct 410 ms 60608 KB Output is correct
27 Correct 427 ms 60704 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 234 ms 3380 KB Output is correct
2 Correct 262 ms 5812 KB Output is correct
3 Correct 249 ms 5976 KB Output is correct
4 Correct 294 ms 5936 KB Output is correct
5 Correct 273 ms 6348 KB Output is correct
6 Correct 242 ms 5772 KB Output is correct
7 Correct 225 ms 3656 KB Output is correct
8 Correct 417 ms 61184 KB Output is correct
9 Correct 470 ms 60836 KB Output is correct
10 Correct 223 ms 3512 KB Output is correct
11 Correct 461 ms 73036 KB Output is correct
12 Correct 472 ms 72968 KB Output is correct
13 Correct 520 ms 72964 KB Output is correct
14 Correct 235 ms 3768 KB Output is correct
15 Correct 437 ms 60740 KB Output is correct
16 Correct 416 ms 61432 KB Output is correct
17 Correct 547 ms 61700 KB Output is correct
18 Correct 460 ms 61692 KB Output is correct
19 Correct 535 ms 67492 KB Output is correct
20 Correct 705 ms 66504 KB Output is correct
21 Correct 436 ms 60736 KB Output is correct
22 Correct 450 ms 60832 KB Output is correct
23 Correct 453 ms 61196 KB Output is correct
24 Correct 490 ms 61388 KB Output is correct
25 Correct 480 ms 64088 KB Output is correct
26 Correct 410 ms 60608 KB Output is correct
27 Correct 427 ms 60704 KB Output is correct
28 Incorrect 246 ms 2768 KB Extra information in the output file
29 Halted 0 ms 0 KB -