oj.uz

Submission #413488

# Submission time Handle Problem Language Result Execution time Memory
413488 2021-05-28T19:21:20 Z Tc14 Inside information (BOI21_servers) C++17
50 / 100
 662 ms 71628 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 = upper_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 229 ms 2956 KB Output is correct
2 Correct 262 ms 4864 KB Output is correct
3 Correct 240 ms 4936 KB Output is correct
4 Correct 281 ms 4976 KB Output is correct
5 Correct 256 ms 5296 KB Output is correct
6 Correct 241 ms 4876 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 229 ms 2956 KB Output is correct
2 Correct 262 ms 4864 KB Output is correct
3 Correct 240 ms 4936 KB Output is correct
4 Correct 281 ms 4976 KB Output is correct
5 Correct 256 ms 5296 KB Output is correct
6 Correct 241 ms 4876 KB Output is correct
7 Incorrect 234 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 220 ms 3004 KB Output is correct
2 Correct 416 ms 59344 KB Output is correct
3 Correct 451 ms 59304 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 220 ms 3004 KB Output is correct
2 Correct 416 ms 59344 KB Output is correct
3 Correct 451 ms 59304 KB Output is correct
4 Incorrect 225 ms 2856 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 222 ms 2924 KB Output is correct
2 Correct 443 ms 71624 KB Output is correct
3 Correct 436 ms 71596 KB Output is correct
4 Correct 507 ms 71520 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 2924 KB Output is correct
2 Correct 443 ms 71624 KB Output is correct
3 Correct 436 ms 71596 KB Output is correct
4 Correct 507 ms 71520 KB Output is correct
5 Incorrect 222 ms 2704 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 2888 KB Output is correct
2 Correct 436 ms 59316 KB Output is correct
3 Correct 402 ms 59908 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 2888 KB Output is correct
2 Correct 436 ms 59316 KB Output is correct
3 Correct 402 ms 59908 KB Output is correct
4 Incorrect 231 ms 2912 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 231 ms 2956 KB Output is correct
2 Correct 448 ms 71532 KB Output is correct
3 Correct 434 ms 71624 KB Output is correct
4 Correct 506 ms 71628 KB Output is correct
5 Correct 234 ms 2988 KB Output is correct
6 Correct 430 ms 59352 KB Output is correct
7 Correct 415 ms 59852 KB Output is correct
8 Correct 535 ms 60248 KB Output is correct
9 Correct 444 ms 60332 KB Output is correct
10 Correct 517 ms 66012 KB Output is correct
11 Correct 646 ms 65076 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 231 ms 2956 KB Output is correct
2 Correct 448 ms 71532 KB Output is correct
3 Correct 434 ms 71624 KB Output is correct
4 Correct 506 ms 71628 KB Output is correct
5 Correct 234 ms 2988 KB Output is correct
6 Correct 430 ms 59352 KB Output is correct
7 Correct 415 ms 59852 KB Output is correct
8 Correct 535 ms 60248 KB Output is correct
9 Correct 444 ms 60332 KB Output is correct
10 Correct 517 ms 66012 KB Output is correct
11 Correct 646 ms 65076 KB Output is correct
12 Incorrect 223 ms 2716 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 236 ms 2880 KB Output is correct
2 Correct 274 ms 4800 KB Output is correct
3 Correct 242 ms 4936 KB Output is correct
4 Correct 277 ms 4948 KB Output is correct
5 Correct 253 ms 5372 KB Output is correct
6 Correct 239 ms 4776 KB Output is correct
7 Correct 227 ms 3044 KB Output is correct
8 Correct 418 ms 59392 KB Output is correct
9 Correct 414 ms 59128 KB Output is correct
10 Correct 223 ms 2768 KB Output is correct
11 Correct 442 ms 71268 KB Output is correct
12 Correct 438 ms 71220 KB Output is correct
13 Correct 535 ms 71220 KB Output is correct
14 Correct 229 ms 2644 KB Output is correct
15 Correct 430 ms 58992 KB Output is correct
16 Correct 407 ms 59468 KB Output is correct
17 Correct 543 ms 59888 KB Output is correct
18 Correct 454 ms 59880 KB Output is correct
19 Correct 521 ms 65820 KB Output is correct
20 Correct 662 ms 64804 KB Output is correct
21 Correct 434 ms 59232 KB Output is correct
22 Correct 427 ms 59148 KB Output is correct
23 Correct 435 ms 59412 KB Output is correct
24 Correct 435 ms 59408 KB Output is correct
25 Correct 486 ms 62312 KB Output is correct
26 Correct 409 ms 58896 KB Output is correct
27 Correct 388 ms 59048 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 236 ms 2880 KB Output is correct
2 Correct 274 ms 4800 KB Output is correct
3 Correct 242 ms 4936 KB Output is correct
4 Correct 277 ms 4948 KB Output is correct
5 Correct 253 ms 5372 KB Output is correct
6 Correct 239 ms 4776 KB Output is correct
7 Correct 227 ms 3044 KB Output is correct
8 Correct 418 ms 59392 KB Output is correct
9 Correct 414 ms 59128 KB Output is correct
10 Correct 223 ms 2768 KB Output is correct
11 Correct 442 ms 71268 KB Output is correct
12 Correct 438 ms 71220 KB Output is correct
13 Correct 535 ms 71220 KB Output is correct
14 Correct 229 ms 2644 KB Output is correct
15 Correct 430 ms 58992 KB Output is correct
16 Correct 407 ms 59468 KB Output is correct
17 Correct 543 ms 59888 KB Output is correct
18 Correct 454 ms 59880 KB Output is correct
19 Correct 521 ms 65820 KB Output is correct
20 Correct 662 ms 64804 KB Output is correct
21 Correct 434 ms 59232 KB Output is correct
22 Correct 427 ms 59148 KB Output is correct
23 Correct 435 ms 59412 KB Output is correct
24 Correct 435 ms 59408 KB Output is correct
25 Correct 486 ms 62312 KB Output is correct
26 Correct 409 ms 58896 KB Output is correct
27 Correct 388 ms 59048 KB Output is correct
28 Incorrect 230 ms 2696 KB Extra information in the output file
29 Halted 0 ms 0 KB -