oj.uz

Submission #413442

# Submission time Handle Problem Language Result Execution time Memory
413442 2021-05-28T17:48:30 Z Tc14 Inside information (BOI21_servers) C++17
50 / 100
 670 ms 74560 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 {
            tie(ignore, d, t, ignore) = Q[i];

            int ans = 1;

            if (Left[d] != 0) {
               ans += distance(Z.begin(), lower_bound(Z.begin() + d - Left[d] + 1, Z.begin() + d + 1, t, greater<int>()));
            }

            if (Right[d] != 0) {
                ans += distance(Z.begin(), lower_bound(Z.begin() + d, Z.begin() + d + Right[d], t));
            }

            cout << ans << endl;
        }
    }

    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 227 ms 3384 KB Output is correct
2 Correct 260 ms 5812 KB Output is correct
3 Correct 248 ms 6012 KB Output is correct
4 Correct 276 ms 5924 KB Output is correct
5 Correct 252 ms 6252 KB Output is correct
6 Correct 238 ms 5788 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 227 ms 3384 KB Output is correct
2 Correct 260 ms 5812 KB Output is correct
3 Correct 248 ms 6012 KB Output is correct
4 Correct 276 ms 5924 KB Output is correct
5 Correct 252 ms 6252 KB Output is correct
6 Correct 238 ms 5788 KB Output is correct
7 Incorrect 227 ms 2872 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 225 ms 3404 KB Output is correct
2 Correct 412 ms 61808 KB Output is correct
3 Correct 417 ms 61960 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 225 ms 3404 KB Output is correct
2 Correct 412 ms 61808 KB Output is correct
3 Correct 417 ms 61960 KB Output is correct
4 Incorrect 229 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 223 ms 3332 KB Output is correct
2 Correct 472 ms 74548 KB Output is correct
3 Correct 452 ms 74548 KB Output is correct
4 Correct 514 ms 74420 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 3332 KB Output is correct
2 Correct 472 ms 74548 KB Output is correct
3 Correct 452 ms 74548 KB Output is correct
4 Correct 514 ms 74420 KB Output is correct
5 Incorrect 223 ms 2836 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 240 ms 3420 KB Output is correct
2 Correct 436 ms 62228 KB Output is correct
3 Correct 404 ms 62776 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 3420 KB Output is correct
2 Correct 436 ms 62228 KB Output is correct
3 Correct 404 ms 62776 KB Output is correct
4 Incorrect 229 ms 3008 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 220 ms 3420 KB Output is correct
2 Correct 443 ms 74464 KB Output is correct
3 Correct 437 ms 74548 KB Output is correct
4 Correct 518 ms 74400 KB Output is correct
5 Correct 232 ms 3584 KB Output is correct
6 Correct 433 ms 62360 KB Output is correct
7 Correct 401 ms 62708 KB Output is correct
8 Correct 541 ms 63148 KB Output is correct
9 Correct 451 ms 63208 KB Output is correct
10 Correct 520 ms 69052 KB Output is correct
11 Correct 670 ms 68156 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 220 ms 3420 KB Output is correct
2 Correct 443 ms 74464 KB Output is correct
3 Correct 437 ms 74548 KB Output is correct
4 Correct 518 ms 74400 KB Output is correct
5 Correct 232 ms 3584 KB Output is correct
6 Correct 433 ms 62360 KB Output is correct
7 Correct 401 ms 62708 KB Output is correct
8 Correct 541 ms 63148 KB Output is correct
9 Correct 451 ms 63208 KB Output is correct
10 Correct 520 ms 69052 KB Output is correct
11 Correct 670 ms 68156 KB Output is correct
12 Incorrect 221 ms 2848 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 227 ms 3456 KB Output is correct
2 Correct 262 ms 5732 KB Output is correct
3 Correct 239 ms 5820 KB Output is correct
4 Correct 289 ms 5912 KB Output is correct
5 Correct 256 ms 6392 KB Output is correct
6 Correct 263 ms 5808 KB Output is correct
7 Correct 223 ms 3568 KB Output is correct
8 Correct 411 ms 61940 KB Output is correct
9 Correct 417 ms 61980 KB Output is correct
10 Correct 222 ms 3620 KB Output is correct
11 Correct 440 ms 74520 KB Output is correct
12 Correct 440 ms 74560 KB Output is correct
13 Correct 516 ms 74392 KB Output is correct
14 Correct 232 ms 3572 KB Output is correct
15 Correct 455 ms 62204 KB Output is correct
16 Correct 397 ms 62788 KB Output is correct
17 Correct 547 ms 63140 KB Output is correct
18 Correct 452 ms 63148 KB Output is correct
19 Correct 535 ms 69000 KB Output is correct
20 Correct 663 ms 68080 KB Output is correct
21 Correct 435 ms 62332 KB Output is correct
22 Correct 437 ms 62416 KB Output is correct
23 Correct 439 ms 62644 KB Output is correct
24 Correct 443 ms 62828 KB Output is correct
25 Correct 520 ms 65520 KB Output is correct
26 Correct 404 ms 62168 KB Output is correct
27 Correct 391 ms 62324 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 227 ms 3456 KB Output is correct
2 Correct 262 ms 5732 KB Output is correct
3 Correct 239 ms 5820 KB Output is correct
4 Correct 289 ms 5912 KB Output is correct
5 Correct 256 ms 6392 KB Output is correct
6 Correct 263 ms 5808 KB Output is correct
7 Correct 223 ms 3568 KB Output is correct
8 Correct 411 ms 61940 KB Output is correct
9 Correct 417 ms 61980 KB Output is correct
10 Correct 222 ms 3620 KB Output is correct
11 Correct 440 ms 74520 KB Output is correct
12 Correct 440 ms 74560 KB Output is correct
13 Correct 516 ms 74392 KB Output is correct
14 Correct 232 ms 3572 KB Output is correct
15 Correct 455 ms 62204 KB Output is correct
16 Correct 397 ms 62788 KB Output is correct
17 Correct 547 ms 63140 KB Output is correct
18 Correct 452 ms 63148 KB Output is correct
19 Correct 535 ms 69000 KB Output is correct
20 Correct 663 ms 68080 KB Output is correct
21 Correct 435 ms 62332 KB Output is correct
22 Correct 437 ms 62416 KB Output is correct
23 Correct 439 ms 62644 KB Output is correct
24 Correct 443 ms 62828 KB Output is correct
25 Correct 520 ms 65520 KB Output is correct
26 Correct 404 ms 62168 KB Output is correct
27 Correct 391 ms 62324 KB Output is correct
28 Incorrect 226 ms 2756 KB Extra information in the output file
29 Halted 0 ms 0 KB -