oj.uz

Submission #658025

# Submission time Handle Problem Language Result Execution time Memory
658025 2022-11-11T22:44:56 Z Lobo Inside information (BOI21_servers) C++17
50 / 100
 826 ms 150348 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 = 3e5+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 == 2) cout << 1 << 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:198: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]
  198 |             for(int i = 0; i < ords.size(); i++) {
      |                            ~~^~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 304 ms 11572 KB Output is correct
2 Correct 299 ms 16156 KB Output is correct
3 Correct 272 ms 16296 KB Output is correct
4 Correct 398 ms 16288 KB Output is correct
5 Correct 313 ms 16576 KB Output is correct
6 Correct 265 ms 16220 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 304 ms 11572 KB Output is correct
2 Correct 299 ms 16156 KB Output is correct
3 Correct 272 ms 16296 KB Output is correct
4 Correct 398 ms 16288 KB Output is correct
5 Correct 313 ms 16576 KB Output is correct
6 Correct 265 ms 16220 KB Output is correct
7 Incorrect 268 ms 11912 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 234 ms 11712 KB Output is correct
2 Correct 489 ms 140588 KB Output is correct
3 Correct 543 ms 140172 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 234 ms 11712 KB Output is correct
2 Correct 489 ms 140588 KB Output is correct
3 Correct 543 ms 140172 KB Output is correct
4 Incorrect 242 ms 11708 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 11664 KB Output is correct
2 Correct 537 ms 150312 KB Output is correct
3 Correct 560 ms 150348 KB Output is correct
4 Correct 663 ms 149616 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 11664 KB Output is correct
2 Correct 537 ms 150312 KB Output is correct
3 Correct 560 ms 150348 KB Output is correct
4 Correct 663 ms 149616 KB Output is correct
5 Incorrect 251 ms 11696 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 280 ms 11644 KB Output is correct
2 Correct 573 ms 141400 KB Output is correct
3 Correct 486 ms 141652 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 11644 KB Output is correct
2 Correct 573 ms 141400 KB Output is correct
3 Correct 486 ms 141652 KB Output is correct
4 Incorrect 270 ms 11644 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 251 ms 11596 KB Output is correct
2 Correct 573 ms 150216 KB Output is correct
3 Correct 585 ms 150272 KB Output is correct
4 Correct 704 ms 149648 KB Output is correct
5 Correct 246 ms 11600 KB Output is correct
6 Correct 525 ms 141424 KB Output is correct
7 Correct 456 ms 141712 KB Output is correct
8 Correct 643 ms 142668 KB Output is correct
9 Correct 576 ms 142544 KB Output is correct
10 Correct 608 ms 146540 KB Output is correct
11 Correct 754 ms 145868 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 251 ms 11596 KB Output is correct
2 Correct 573 ms 150216 KB Output is correct
3 Correct 585 ms 150272 KB Output is correct
4 Correct 704 ms 149648 KB Output is correct
5 Correct 246 ms 11600 KB Output is correct
6 Correct 525 ms 141424 KB Output is correct
7 Correct 456 ms 141712 KB Output is correct
8 Correct 643 ms 142668 KB Output is correct
9 Correct 576 ms 142544 KB Output is correct
10 Correct 608 ms 146540 KB Output is correct
11 Correct 754 ms 145868 KB Output is correct
12 Incorrect 237 ms 11596 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 248 ms 11588 KB Output is correct
2 Correct 320 ms 15772 KB Output is correct
3 Correct 261 ms 15896 KB Output is correct
4 Correct 363 ms 15944 KB Output is correct
5 Correct 311 ms 16176 KB Output is correct
6 Correct 261 ms 15816 KB Output is correct
7 Correct 236 ms 11648 KB Output is correct
8 Correct 487 ms 140292 KB Output is correct
9 Correct 489 ms 140300 KB Output is correct
10 Correct 240 ms 11588 KB Output is correct
11 Correct 570 ms 150252 KB Output is correct
12 Correct 590 ms 150344 KB Output is correct
13 Correct 695 ms 149792 KB Output is correct
14 Correct 252 ms 11636 KB Output is correct
15 Correct 536 ms 141564 KB Output is correct
16 Correct 490 ms 141688 KB Output is correct
17 Correct 702 ms 142516 KB Output is correct
18 Correct 533 ms 142528 KB Output is correct
19 Correct 628 ms 146596 KB Output is correct
20 Correct 826 ms 145932 KB Output is correct
21 Correct 515 ms 140212 KB Output is correct
22 Correct 572 ms 141088 KB Output is correct
23 Correct 527 ms 141260 KB Output is correct
24 Correct 597 ms 141088 KB Output is correct
25 Correct 669 ms 143192 KB Output is correct
26 Correct 546 ms 140732 KB Output is correct
27 Correct 495 ms 140820 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 248 ms 11588 KB Output is correct
2 Correct 320 ms 15772 KB Output is correct
3 Correct 261 ms 15896 KB Output is correct
4 Correct 363 ms 15944 KB Output is correct
5 Correct 311 ms 16176 KB Output is correct
6 Correct 261 ms 15816 KB Output is correct
7 Correct 236 ms 11648 KB Output is correct
8 Correct 487 ms 140292 KB Output is correct
9 Correct 489 ms 140300 KB Output is correct
10 Correct 240 ms 11588 KB Output is correct
11 Correct 570 ms 150252 KB Output is correct
12 Correct 590 ms 150344 KB Output is correct
13 Correct 695 ms 149792 KB Output is correct
14 Correct 252 ms 11636 KB Output is correct
15 Correct 536 ms 141564 KB Output is correct
16 Correct 490 ms 141688 KB Output is correct
17 Correct 702 ms 142516 KB Output is correct
18 Correct 533 ms 142528 KB Output is correct
19 Correct 628 ms 146596 KB Output is correct
20 Correct 826 ms 145932 KB Output is correct
21 Correct 515 ms 140212 KB Output is correct
22 Correct 572 ms 141088 KB Output is correct
23 Correct 527 ms 141260 KB Output is correct
24 Correct 597 ms 141088 KB Output is correct
25 Correct 669 ms 143192 KB Output is correct
26 Correct 546 ms 140732 KB Output is correct
27 Correct 495 ms 140820 KB Output is correct
28 Incorrect 290 ms 11928 KB Extra information in the output file
29 Halted 0 ms 0 KB -