oj.uz

Submission #657457

# Submission time Handle Problem Language Result Execution time Memory
657457 2022-11-09T21:23:25 Z Lobo Inside information (BOI21_servers) C++17
50 / 100
 762 ms 143364 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

const int inf = 1e9+10;
const int maxn = 2e5+10;

int n, k, h[maxn];
int pp[maxn][25], pmn[maxn][25], pmx[maxn][25], pin[maxn][25], pde[maxn][25];
vector<pair<int,int>> g[maxn];

void dfs(int u, int ant) {
    for(int i = 1; i <= 20; i++) {
        if(pp[u][i-1] == -1) {
            pp[u][i] = -1;
            pmn[u][i] = pmn[u][i-1];
            pmx[u][i] = pmx[u][i-1];
            pin[u][i] = pin[u][i-1];
            pde[u][i] = pde[u][i-1];
        }
        else {
            pp[u][i] = pp[pp[u][i-1]][i-1];
            pmn[u][i] = min(pmn[u][i-1],pmn[pp[u][i-1]][i-1]);
            pmx[u][i] = max(pmx[u][i-1],pmx[pp[u][i-1]][i-1]);

            pde[u][i] = pde[u][i-1]&pde[pp[u][i-1]][i-1]&(pmn[u][i-1] > pmx[pp[u][i-1]][i-1]);
            pin[u][i] = pin[u][i-1]&pin[pp[u][i-1]][i-1]&(pmx[u][i-1] < pmn[pp[u][i-1]][i-1]);
        }
    }

    for(auto V : g[u]) if(V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        pmn[v][0] = w;
        pmx[v][0] = w;
        pin[v][0] = 1;
        pde[v][0] = 1;
        pp[v][0] = u;
        h[v] = h[u]+1;
        dfs(v,u);
    }
}

int lca(int u, int v) {
    if(h[v] > h[u]) {
        swap(u,v);
    }

    for(int i = 20; i >= 0; i--) {
        if(pp[u][i] != -1 && h[pp[u][i]] >= h[v]) u = pp[u][i];
    }

    if(u == v) return u;

    for(int i = 20; i >= 0; i--) {
        if(pp[u][i] != -1 && pp[v][i] != -1 && pp[u][i] != pp[v][i]) {
            u = pp[u][i];
            v = pp[v][i];
        }
    }
    return pp[u][0];
}

int32_t main() {
    // freopen("in.in", "r", stdin);
    cin >> n >> k;
    vector<pair<pair<int,int>,pair<int,int>>> qrys;
    for(int i = 1; i <= n+k-1; i++) {
        char op; cin >> op;
        if(op == 'S') {
            int u,v;cin >> u >> v;
            g[u].pb(mp(v,i));
            g[v].pb(mp(u,i));
        }
        else if(op == 'Q') {
            int u,v; cin >> u >> v;
            qrys.pb(mp(mp(0,i),mp(u,v)));
        }
    }

    pp[1][0] = -1;
    pmn[1][0] = inf;
    pmx[1][0] = -inf;
    pin[1][0] = 1;
    pde[1][0] = 1;
    dfs(1,1);

    for(auto X : qrys) {
        int w = X.fr.sc;
        int u = X.sc.sc;
        int v = X.sc.fr;

        int lc = lca(u,v);
        string ans = "yes";

        vector<int> ordu, ordv, ords;
        // while(u != lc) {
        //     ordu.pb(pmn[u][0]);
        //     u = pp[u][0];
        // }
        for(int i = 20; i >= 0; i--) {
            if(pp[u][i] != -1 && h[pp[u][i]] >= h[lc]) {
                if(pin[u][i] == 0) ans = "no";
                ordu.pb(pmn[u][i]);
                ordu.pb(pmx[u][i]);
                u = pp[u][i];
            }
        }

        // while(v != lc) {
        //     ordv.pb(pmn[v][0]);
        //     v = pp[v][0];
        // }
        for(int i = 20; i >= 0; i--) {
            if(pp[v][i] != -1 && h[pp[v][i]] >= h[lc]) {
                if(pde[v][i] == 0) ans = "no";
                ordv.pb(pmx[v][i]);
                ordv.pb(pmn[v][i]);
                v = pp[v][i];
            }
        }

        for(auto x : ordu) ords.pb(x);
        reverse(all(ordv));
        for(auto x : ordv) ords.pb(x);

        for(int i = 0; i < ords.size(); i++) {
            if(ords[i] > w) ans = "no";
            if(i != 0 && ords[i] < ords[i-1]) ans = "no";
        }
        cout << ans << endl;


    }
}

Compilation message

servers.cpp: In function 'int32_t main()':
servers.cpp:132:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for(int i = 0; i < ords.size(); i++) {
      |                        ~~^~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 234 ms 9292 KB Output is correct
2 Correct 297 ms 13360 KB Output is correct
3 Correct 254 ms 13360 KB Output is correct
4 Correct 352 ms 13460 KB Output is correct
5 Correct 304 ms 13512 KB Output is correct
6 Correct 254 ms 13380 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 234 ms 9292 KB Output is correct
2 Correct 297 ms 13360 KB Output is correct
3 Correct 254 ms 13360 KB Output is correct
4 Correct 352 ms 13460 KB Output is correct
5 Correct 304 ms 13512 KB Output is correct
6 Correct 254 ms 13380 KB Output is correct
7 Incorrect 224 ms 9172 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 233 ms 9280 KB Output is correct
2 Correct 493 ms 133108 KB Output is correct
3 Correct 464 ms 133116 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 233 ms 9280 KB Output is correct
2 Correct 493 ms 133108 KB Output is correct
3 Correct 464 ms 133116 KB Output is correct
4 Incorrect 211 ms 9228 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 234 ms 9332 KB Output is correct
2 Correct 519 ms 143196 KB Output is correct
3 Correct 509 ms 143248 KB Output is correct
4 Correct 652 ms 142564 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 9332 KB Output is correct
2 Correct 519 ms 143196 KB Output is correct
3 Correct 509 ms 143248 KB Output is correct
4 Correct 652 ms 142564 KB Output is correct
5 Incorrect 220 ms 9964 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 245 ms 9328 KB Output is correct
2 Correct 509 ms 134516 KB Output is correct
3 Correct 445 ms 134616 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 9328 KB Output is correct
2 Correct 509 ms 134516 KB Output is correct
3 Correct 445 ms 134616 KB Output is correct
4 Incorrect 224 ms 9208 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 244 ms 9244 KB Output is correct
2 Correct 511 ms 143364 KB Output is correct
3 Correct 512 ms 143276 KB Output is correct
4 Correct 640 ms 142476 KB Output is correct
5 Correct 237 ms 10264 KB Output is correct
6 Correct 499 ms 137768 KB Output is correct
7 Correct 443 ms 137900 KB Output is correct
8 Correct 684 ms 138780 KB Output is correct
9 Correct 523 ms 138844 KB Output is correct
10 Correct 600 ms 142804 KB Output is correct
11 Correct 742 ms 142128 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 244 ms 9244 KB Output is correct
2 Correct 511 ms 143364 KB Output is correct
3 Correct 512 ms 143276 KB Output is correct
4 Correct 640 ms 142476 KB Output is correct
5 Correct 237 ms 10264 KB Output is correct
6 Correct 499 ms 137768 KB Output is correct
7 Correct 443 ms 137900 KB Output is correct
8 Correct 684 ms 138780 KB Output is correct
9 Correct 523 ms 138844 KB Output is correct
10 Correct 600 ms 142804 KB Output is correct
11 Correct 742 ms 142128 KB Output is correct
12 Incorrect 261 ms 9916 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 244 ms 9424 KB Output is correct
2 Correct 320 ms 13368 KB Output is correct
3 Correct 249 ms 13308 KB Output is correct
4 Correct 345 ms 13376 KB Output is correct
5 Correct 306 ms 13652 KB Output is correct
6 Correct 255 ms 13232 KB Output is correct
7 Correct 228 ms 9332 KB Output is correct
8 Correct 475 ms 133340 KB Output is correct
9 Correct 458 ms 133336 KB Output is correct
10 Correct 235 ms 9280 KB Output is correct
11 Correct 524 ms 143284 KB Output is correct
12 Correct 542 ms 143240 KB Output is correct
13 Correct 662 ms 142576 KB Output is correct
14 Correct 243 ms 10244 KB Output is correct
15 Correct 493 ms 137680 KB Output is correct
16 Correct 455 ms 138008 KB Output is correct
17 Correct 637 ms 138740 KB Output is correct
18 Correct 519 ms 138752 KB Output is correct
19 Correct 567 ms 142828 KB Output is correct
20 Correct 762 ms 142028 KB Output is correct
21 Correct 489 ms 136664 KB Output is correct
22 Correct 483 ms 137440 KB Output is correct
23 Correct 514 ms 137240 KB Output is correct
24 Correct 496 ms 137320 KB Output is correct
25 Correct 535 ms 139388 KB Output is correct
26 Correct 468 ms 137204 KB Output is correct
27 Correct 443 ms 137160 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 244 ms 9424 KB Output is correct
2 Correct 320 ms 13368 KB Output is correct
3 Correct 249 ms 13308 KB Output is correct
4 Correct 345 ms 13376 KB Output is correct
5 Correct 306 ms 13652 KB Output is correct
6 Correct 255 ms 13232 KB Output is correct
7 Correct 228 ms 9332 KB Output is correct
8 Correct 475 ms 133340 KB Output is correct
9 Correct 458 ms 133336 KB Output is correct
10 Correct 235 ms 9280 KB Output is correct
11 Correct 524 ms 143284 KB Output is correct
12 Correct 542 ms 143240 KB Output is correct
13 Correct 662 ms 142576 KB Output is correct
14 Correct 243 ms 10244 KB Output is correct
15 Correct 493 ms 137680 KB Output is correct
16 Correct 455 ms 138008 KB Output is correct
17 Correct 637 ms 138740 KB Output is correct
18 Correct 519 ms 138752 KB Output is correct
19 Correct 567 ms 142828 KB Output is correct
20 Correct 762 ms 142028 KB Output is correct
21 Correct 489 ms 136664 KB Output is correct
22 Correct 483 ms 137440 KB Output is correct
23 Correct 514 ms 137240 KB Output is correct
24 Correct 496 ms 137320 KB Output is correct
25 Correct 535 ms 139388 KB Output is correct
26 Correct 468 ms 137204 KB Output is correct
27 Correct 443 ms 137160 KB Output is correct
28 Incorrect 222 ms 9904 KB Extra information in the output file
29 Halted 0 ms 0 KB -