oj.uz

Submission #556731

# Submission time Handle Problem Language Result Execution time Memory
556731 2022-05-03T19:32:27 Z RaresFelix Inside information (BOI21_servers) C++17
50 / 100
 378 ms 67992 KB 
#include <bits/stdc++.h>
#define MN 120071
#define MK 20
using namespace std;
int n, k;
vector<pair<int, int> > L0[MN];
vector<int> L[MN];
vector<tuple<int, int, int, int> > Queries;
namespace BASIC {
    int Niv[MN], Val[MN], Par[MN], NiceUp[MN]; 
    int Maxi[MK][MN], Nice[2][MK][MN], Stramos[MK][MN];
    void init() {
        ///aleg rad arbitrar in 1
        function<void(int, int, int, int)> dfs0 = [&](int u, int p, int niv, int val) {
            Val[u] = val;
            Niv[u] = niv;
            Par[u] = p;
            for(auto &[it, w] : L0[u]) if(it != p) {
                dfs0(it, u, niv + 1, w);
            } 
            if(Niv[u] > 1) NiceUp[u] = Val[u] < Val[p];
        };
        dfs0(1, 0, 0, 0);
        for(int i = 1; i <= n; ++i) Stramos[0][i] = Par[i];
        for(int k = 1; k < MK; ++k) {
            for(int i = 1; i <= n; ++i)
                Stramos[k][i] = Stramos[k-1][Stramos[k-1][i]];
        }
        for(int i = 1; i <= n; ++i)
            Nice[0][0][i] = NiceUp[i] ^ 1, Nice[1][0][i] = NiceUp[i];
        for(int d = 0; d < 2; ++d) {
            for(int k = 1; k < MK; ++k) {
                for(int i = 1; i <= n; ++i) {
                    Nice[d][k][i] = Nice[d][k-1][i] & Nice[d][k-1][Stramos[k-1][i]];
                }
            }
        }
        for(int i = 1; i <= n; ++i)
            Maxi[0][i] = Val[i];
        for(int k = 1; k < MK; ++k)
            for(int i = 1; i <= n; ++i)
                Maxi[k][i] = max(Maxi[k-1][i], Maxi[k-1][Stramos[k-1][i]]);
    }
    bool is_okay(int u, int v) { ///!!! ORDER IS VERY IMPORTANT U => V
        bool rez = 1;
        if(Niv[u] > Niv[v]) {
            for(int k = MK - 1; k >= 0; --k) {
                if((Niv[u] - Niv[v] - 1) & (1 << k)) {
                    rez &= Nice[1][k][u];
                    u = Stramos[k][u];
                }
            }
            if(Par[u] != v) rez &= Nice[1][0][u]; 
            u = Par[u];
        } else if (Niv[u] < Niv[v]) {
            for(int k = MK - 1; k >= 0; --k) {
                if((Niv[v] - Niv[u] - 1) & (1 << k)) {
                    rez &= Nice[0][k][v];
                   // printf("debug %d %d %d -- ", k, v, rez);
                    //printf("debug %d %d %d\n", Nice[0][0][v], Nice[0][1][v], Stramos[1][v]);
                    
                    v = Stramos[k][v];
                }
            }
            if(Par[v] != u) rez &= Nice[0][0][v];
            v = Par[v];
        }
        ///acum sunt la acelasi nivel
        assert(Niv[u] == Niv[v]);
        if(v == u || !rez) return rez;
        for(int k = MK - 1; k >= 0; --k) {
            if(Stramos[k][u] != Stramos[k][v]) {
                rez &= Nice[0][k][v];
                rez &= Nice[1][k][u];
                v = Stramos[k][v];
                u = Stramos[k][u];
            }
        }
        if(u != v) rez &= Val[u] < Val[v];
        return rez;
    }
    int max_on_path(int u, int v) {
        int rez = 0;
        if(Niv[u] < Niv[v]) swap(u, v);
        if(Niv[u] != Niv[v])
            for(int k = MK - 1; k >= 0; --k)
                if((Niv[u] - Niv[v] - 1) & (1 << k)) {
                    rez = max(rez, Maxi[k][u]);
                    u = Stramos[k][u];
                }
        if(Niv[u] != Niv[v]) {
            rez = max(rez, Maxi[0][u]);
            u = Par[u];
        }
        assert(Niv[u] == Niv[v]);
        for(int k = MK - 1; k >= 0; --k)
            if(Stramos[k][u] != Stramos[k][v]) {
                rez = max(rez, Maxi[k][u]);
                rez = max(rez, Maxi[k][v]);
                u = Stramos[k][u];
                v = Stramos[k][v];
            }
        if(u != v) rez = max({rez, Val[u], Val[v]});
        return rez;

    }
}

int main() {
    //cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    for(int i = 1, a, b; i <= n + k - 1; ++i) {
        char tip;
        cin >> tip;
        if(tip == 'S') {
            cin >> a >> b;
            L0[a].push_back({b, i});
            L0[b].push_back({a, i});
        } else if(tip == 'Q') {
            cin >> a >> b;
            Queries.push_back({0, a, b, i});
        } else {
            cin >> a;
            Queries.push_back({1, a, 0, i});
        }
    }
    BASIC::init();
    for(auto &[tip, a, b, id] : Queries) {
        if(tip == 0) {
            int ok = BASIC::is_okay(b, a);
            ok &= BASIC::max_on_path(b, a) < id;
            cout << (ok ? "yes\n" : "no\n");
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 9640 KB Output is correct
2 Correct 93 ms 11324 KB Output is correct
3 Correct 86 ms 11528 KB Output is correct
4 Correct 122 ms 11520 KB Output is correct
5 Correct 111 ms 11864 KB Output is correct
6 Correct 85 ms 11368 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 70 ms 9640 KB Output is correct
2 Correct 93 ms 11324 KB Output is correct
3 Correct 86 ms 11528 KB Output is correct
4 Correct 122 ms 11520 KB Output is correct
5 Correct 111 ms 11864 KB Output is correct
6 Correct 85 ms 11368 KB Output is correct
7 Incorrect 67 ms 9552 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 68 ms 9524 KB Output is correct
2 Correct 244 ms 54688 KB Output is correct
3 Correct 214 ms 54696 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 9524 KB Output is correct
2 Correct 244 ms 54688 KB Output is correct
3 Correct 214 ms 54696 KB Output is correct
4 Incorrect 61 ms 9580 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 76 ms 9604 KB Output is correct
2 Correct 331 ms 67900 KB Output is correct
3 Correct 250 ms 67976 KB Output is correct
4 Correct 284 ms 67784 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 9604 KB Output is correct
2 Correct 331 ms 67900 KB Output is correct
3 Correct 250 ms 67976 KB Output is correct
4 Correct 284 ms 67784 KB Output is correct
5 Incorrect 84 ms 9512 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 66 ms 9540 KB Output is correct
2 Correct 289 ms 55656 KB Output is correct
3 Correct 285 ms 56132 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 9540 KB Output is correct
2 Correct 289 ms 55656 KB Output is correct
3 Correct 285 ms 56132 KB Output is correct
4 Incorrect 63 ms 9552 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 72 ms 9520 KB Output is correct
2 Correct 308 ms 67992 KB Output is correct
3 Correct 281 ms 67912 KB Output is correct
4 Correct 295 ms 67880 KB Output is correct
5 Correct 81 ms 9508 KB Output is correct
6 Correct 231 ms 55584 KB Output is correct
7 Correct 286 ms 56232 KB Output is correct
8 Correct 300 ms 56532 KB Output is correct
9 Correct 292 ms 56480 KB Output is correct
10 Correct 279 ms 62420 KB Output is correct
11 Correct 374 ms 61496 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9520 KB Output is correct
2 Correct 308 ms 67992 KB Output is correct
3 Correct 281 ms 67912 KB Output is correct
4 Correct 295 ms 67880 KB Output is correct
5 Correct 81 ms 9508 KB Output is correct
6 Correct 231 ms 55584 KB Output is correct
7 Correct 286 ms 56232 KB Output is correct
8 Correct 300 ms 56532 KB Output is correct
9 Correct 292 ms 56480 KB Output is correct
10 Correct 279 ms 62420 KB Output is correct
11 Correct 374 ms 61496 KB Output is correct
12 Incorrect 87 ms 9516 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 71 ms 9516 KB Output is correct
2 Correct 105 ms 11416 KB Output is correct
3 Correct 93 ms 11564 KB Output is correct
4 Correct 120 ms 11560 KB Output is correct
5 Correct 105 ms 11920 KB Output is correct
6 Correct 84 ms 11364 KB Output is correct
7 Correct 67 ms 9636 KB Output is correct
8 Correct 234 ms 54736 KB Output is correct
9 Correct 224 ms 54692 KB Output is correct
10 Correct 71 ms 9532 KB Output is correct
11 Correct 285 ms 67932 KB Output is correct
12 Correct 252 ms 67840 KB Output is correct
13 Correct 294 ms 67768 KB Output is correct
14 Correct 68 ms 9528 KB Output is correct
15 Correct 239 ms 55600 KB Output is correct
16 Correct 242 ms 56188 KB Output is correct
17 Correct 333 ms 56576 KB Output is correct
18 Correct 269 ms 56576 KB Output is correct
19 Correct 274 ms 62368 KB Output is correct
20 Correct 378 ms 61496 KB Output is correct
21 Correct 242 ms 55756 KB Output is correct
22 Correct 217 ms 55832 KB Output is correct
23 Correct 241 ms 56052 KB Output is correct
24 Correct 247 ms 56148 KB Output is correct
25 Correct 262 ms 58960 KB Output is correct
26 Correct 235 ms 55536 KB Output is correct
27 Correct 226 ms 55760 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 71 ms 9516 KB Output is correct
2 Correct 105 ms 11416 KB Output is correct
3 Correct 93 ms 11564 KB Output is correct
4 Correct 120 ms 11560 KB Output is correct
5 Correct 105 ms 11920 KB Output is correct
6 Correct 84 ms 11364 KB Output is correct
7 Correct 67 ms 9636 KB Output is correct
8 Correct 234 ms 54736 KB Output is correct
9 Correct 224 ms 54692 KB Output is correct
10 Correct 71 ms 9532 KB Output is correct
11 Correct 285 ms 67932 KB Output is correct
12 Correct 252 ms 67840 KB Output is correct
13 Correct 294 ms 67768 KB Output is correct
14 Correct 68 ms 9528 KB Output is correct
15 Correct 239 ms 55600 KB Output is correct
16 Correct 242 ms 56188 KB Output is correct
17 Correct 333 ms 56576 KB Output is correct
18 Correct 269 ms 56576 KB Output is correct
19 Correct 274 ms 62368 KB Output is correct
20 Correct 378 ms 61496 KB Output is correct
21 Correct 242 ms 55756 KB Output is correct
22 Correct 217 ms 55832 KB Output is correct
23 Correct 241 ms 56052 KB Output is correct
24 Correct 247 ms 56148 KB Output is correct
25 Correct 262 ms 58960 KB Output is correct
26 Correct 235 ms 55536 KB Output is correct
27 Correct 226 ms 55760 KB Output is correct
28 Incorrect 67 ms 9516 KB Extra information in the output file
29 Halted 0 ms 0 KB -