oj.uz

Submission #658023

# Submission time Handle Problem Language Result Execution time Memory
658023 2022-11-11T22:41:06 Z Lobo Inside information (BOI21_servers) C++17
50 / 100
 910 ms 148836 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];
int dp[maxn];
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));
            qrys.pb(mp(mp(0,i),mp(u,v)));
        }
        else if(op == 'Q') {
            int u,v; cin >> u >> v;
            qrys.pb(mp(mp(1,i),mp(u,v)));
        }
        else if(op == 'C') {
            int v; cin >> v;
            qrys.pb(mp(mp(2,i),mp(v,0)));
        }
    }

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

    for(int i = 1; i <= n; i++) dp[i] = 1;

    for(auto X : qrys) {
        int optp = X.fr.fr;
        // if(optp == 0) {
        //     int u = X.sc.fr;
        //     int v = X.sc.sc;
        //     if(h[v] < h[u]) swap(u,v);
        //     // u is parent of v

        //     int p = v;
        //     int antw = inf;
        //     while(pp[p][0] != -1 && pmn[p][0] < antw) {
        //         antw = pmn[p][0];
        //         p = pp[p][0];
        //     }

        //     // p is the lowest ancestor of v that v...p is decreacing, so u...p can reach v

        //     int x = v;
        //     while(x != p) {
        //         x = pp[x][0];
        //         dp[x]+= 1;
        //     }

        //     // cout << "  " << u << " " << v << endl;
        //     // for(int i = 1; i <= n; i++) {
        //     //     cout << i << " " << dp[i] << endl;
        //     // }
        // }
        // if(optp == 2) {
        //     int v = X.sc.fr;
        //     int w = X.fr.sc;

        //     int p = v;
        //     int antw = 0;
        //     while(pp[p][0] != -1 && pmx[p][0] < w && pmn[p][0] > antw) {
        //         antw = pmn[p][0];
        //         p = pp[p][0];
        //     }

        //     int x = v;
        //     int ans = 0;
        //     antw = 0;
        //     while(h[x] >= h[p] && x != -1) {
        //         ans++;
        //         for(auto S : g[x]) if(S.fr != pp[x][0]) {
        //             int s = S.fr;
        //             int w1 = S.sc;
        //             if(w1 > antw) {
        //                 ans+= dp[s];
        //             }
        //         }
        //         antw = pmx[x][0];
        //         x = pp[x][0];
        //     }

        //     cout << ans << endl;
        // }
        if(optp == 1) {
            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:197:30: 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]
  197 |             for(int i = 0; i < ords.size(); i++) {
      |                            ~~^~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 251 ms 9388 KB Output is correct
2 Correct 297 ms 13572 KB Output is correct
3 Correct 263 ms 13548 KB Output is correct
4 Correct 351 ms 13520 KB Output is correct
5 Correct 341 ms 13744 KB Output is correct
6 Correct 256 ms 13592 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 251 ms 9388 KB Output is correct
2 Correct 297 ms 13572 KB Output is correct
3 Correct 263 ms 13548 KB Output is correct
4 Correct 351 ms 13520 KB Output is correct
5 Correct 341 ms 13744 KB Output is correct
6 Correct 256 ms 13592 KB Output is correct
7 Incorrect 237 ms 9388 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 273 ms 9252 KB Output is correct
2 Correct 500 ms 137936 KB Output is correct
3 Correct 528 ms 137920 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 273 ms 9252 KB Output is correct
2 Correct 500 ms 137936 KB Output is correct
3 Correct 528 ms 137920 KB Output is correct
4 Incorrect 249 ms 9328 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 254 ms 9336 KB Output is correct
2 Correct 610 ms 147920 KB Output is correct
3 Correct 537 ms 148044 KB Output is correct
4 Correct 643 ms 147460 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 9336 KB Output is correct
2 Correct 610 ms 147920 KB Output is correct
3 Correct 537 ms 148044 KB Output is correct
4 Correct 643 ms 147460 KB Output is correct
5 Incorrect 240 ms 9896 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 238 ms 9288 KB Output is correct
2 Correct 541 ms 139072 KB Output is correct
3 Correct 456 ms 139540 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 9288 KB Output is correct
2 Correct 541 ms 139072 KB Output is correct
3 Correct 456 ms 139540 KB Output is correct
4 Incorrect 246 ms 9336 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 240 ms 9248 KB Output is correct
2 Correct 566 ms 148012 KB Output is correct
3 Correct 561 ms 147932 KB Output is correct
4 Correct 656 ms 147392 KB Output is correct
5 Correct 244 ms 9948 KB Output is correct
6 Correct 515 ms 139748 KB Output is correct
7 Correct 497 ms 139980 KB Output is correct
8 Correct 679 ms 140940 KB Output is correct
9 Correct 547 ms 140768 KB Output is correct
10 Correct 607 ms 144952 KB Output is correct
11 Correct 774 ms 144084 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 240 ms 9248 KB Output is correct
2 Correct 566 ms 148012 KB Output is correct
3 Correct 561 ms 147932 KB Output is correct
4 Correct 656 ms 147392 KB Output is correct
5 Correct 244 ms 9948 KB Output is correct
6 Correct 515 ms 139748 KB Output is correct
7 Correct 497 ms 139980 KB Output is correct
8 Correct 679 ms 140940 KB Output is correct
9 Correct 547 ms 140768 KB Output is correct
10 Correct 607 ms 144952 KB Output is correct
11 Correct 774 ms 144084 KB Output is correct
12 Incorrect 229 ms 9832 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 9320 KB Output is correct
2 Correct 347 ms 13440 KB Output is correct
3 Correct 251 ms 13632 KB Output is correct
4 Correct 421 ms 13616 KB Output is correct
5 Correct 326 ms 13748 KB Output is correct
6 Correct 341 ms 13428 KB Output is correct
7 Correct 238 ms 9492 KB Output is correct
8 Correct 594 ms 137804 KB Output is correct
9 Correct 565 ms 138440 KB Output is correct
10 Correct 256 ms 9912 KB Output is correct
11 Correct 603 ms 148836 KB Output is correct
12 Correct 647 ms 148776 KB Output is correct
13 Correct 780 ms 148132 KB Output is correct
14 Correct 280 ms 10188 KB Output is correct
15 Correct 679 ms 140208 KB Output is correct
16 Correct 520 ms 140552 KB Output is correct
17 Correct 829 ms 141076 KB Output is correct
18 Correct 633 ms 141160 KB Output is correct
19 Correct 666 ms 145256 KB Output is correct
20 Correct 910 ms 144684 KB Output is correct
21 Correct 605 ms 139076 KB Output is correct
22 Correct 584 ms 139880 KB Output is correct
23 Correct 542 ms 139880 KB Output is correct
24 Correct 600 ms 139900 KB Output is correct
25 Correct 664 ms 141828 KB Output is correct
26 Correct 506 ms 139564 KB Output is correct
27 Correct 534 ms 139500 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 244 ms 9320 KB Output is correct
2 Correct 347 ms 13440 KB Output is correct
3 Correct 251 ms 13632 KB Output is correct
4 Correct 421 ms 13616 KB Output is correct
5 Correct 326 ms 13748 KB Output is correct
6 Correct 341 ms 13428 KB Output is correct
7 Correct 238 ms 9492 KB Output is correct
8 Correct 594 ms 137804 KB Output is correct
9 Correct 565 ms 138440 KB Output is correct
10 Correct 256 ms 9912 KB Output is correct
11 Correct 603 ms 148836 KB Output is correct
12 Correct 647 ms 148776 KB Output is correct
13 Correct 780 ms 148132 KB Output is correct
14 Correct 280 ms 10188 KB Output is correct
15 Correct 679 ms 140208 KB Output is correct
16 Correct 520 ms 140552 KB Output is correct
17 Correct 829 ms 141076 KB Output is correct
18 Correct 633 ms 141160 KB Output is correct
19 Correct 666 ms 145256 KB Output is correct
20 Correct 910 ms 144684 KB Output is correct
21 Correct 605 ms 139076 KB Output is correct
22 Correct 584 ms 139880 KB Output is correct
23 Correct 542 ms 139880 KB Output is correct
24 Correct 600 ms 139900 KB Output is correct
25 Correct 664 ms 141828 KB Output is correct
26 Correct 506 ms 139564 KB Output is correct
27 Correct 534 ms 139500 KB Output is correct
28 Incorrect 276 ms 9996 KB Extra information in the output file
29 Halted 0 ms 0 KB -