oj.uz

Submission #658027

# Submission time Handle Problem Language Result Execution time Memory
658027 2022-11-11T22:48:20 Z Lobo Inside information (BOI21_servers) C++17
50 / 100
 748 ms 150832 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 238 ms 11696 KB Output is correct
2 Correct 298 ms 16516 KB Output is correct
3 Correct 255 ms 16640 KB Output is correct
4 Correct 352 ms 16696 KB Output is correct
5 Correct 310 ms 16688 KB Output is correct
6 Correct 265 ms 16300 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 238 ms 11696 KB Output is correct
2 Correct 298 ms 16516 KB Output is correct
3 Correct 255 ms 16640 KB Output is correct
4 Correct 352 ms 16696 KB Output is correct
5 Correct 310 ms 16688 KB Output is correct
6 Correct 265 ms 16300 KB Output is correct
7 Incorrect 240 ms 11956 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 240 ms 11640 KB Output is correct
2 Correct 480 ms 140788 KB Output is correct
3 Correct 479 ms 140692 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 240 ms 11640 KB Output is correct
2 Correct 480 ms 140788 KB Output is correct
3 Correct 479 ms 140692 KB Output is correct
4 Incorrect 228 ms 11924 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 266 ms 11608 KB Output is correct
2 Correct 518 ms 150704 KB Output is correct
3 Correct 528 ms 150668 KB Output is correct
4 Correct 658 ms 150100 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 11608 KB Output is correct
2 Correct 518 ms 150704 KB Output is correct
3 Correct 528 ms 150668 KB Output is correct
4 Correct 658 ms 150100 KB Output is correct
5 Incorrect 235 ms 11824 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 246 ms 11632 KB Output is correct
2 Correct 498 ms 141744 KB Output is correct
3 Correct 454 ms 142120 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 11632 KB Output is correct
2 Correct 498 ms 141744 KB Output is correct
3 Correct 454 ms 142120 KB Output is correct
4 Incorrect 235 ms 11824 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 246 ms 11740 KB Output is correct
2 Correct 525 ms 150724 KB Output is correct
3 Correct 529 ms 150592 KB Output is correct
4 Correct 637 ms 149920 KB Output is correct
5 Correct 249 ms 11824 KB Output is correct
6 Correct 490 ms 141768 KB Output is correct
7 Correct 446 ms 142116 KB Output is correct
8 Correct 624 ms 142832 KB Output is correct
9 Correct 537 ms 143040 KB Output is correct
10 Correct 583 ms 147028 KB Output is correct
11 Correct 739 ms 146236 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 246 ms 11740 KB Output is correct
2 Correct 525 ms 150724 KB Output is correct
3 Correct 529 ms 150592 KB Output is correct
4 Correct 637 ms 149920 KB Output is correct
5 Correct 249 ms 11824 KB Output is correct
6 Correct 490 ms 141768 KB Output is correct
7 Correct 446 ms 142116 KB Output is correct
8 Correct 624 ms 142832 KB Output is correct
9 Correct 537 ms 143040 KB Output is correct
10 Correct 583 ms 147028 KB Output is correct
11 Correct 739 ms 146236 KB Output is correct
12 Incorrect 241 ms 11848 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 246 ms 11836 KB Output is correct
2 Correct 315 ms 16144 KB Output is correct
3 Correct 249 ms 16340 KB Output is correct
4 Correct 349 ms 16448 KB Output is correct
5 Correct 314 ms 16556 KB Output is correct
6 Correct 254 ms 16232 KB Output is correct
7 Correct 226 ms 11868 KB Output is correct
8 Correct 475 ms 140756 KB Output is correct
9 Correct 468 ms 140708 KB Output is correct
10 Correct 236 ms 12024 KB Output is correct
11 Correct 520 ms 150832 KB Output is correct
12 Correct 518 ms 150752 KB Output is correct
13 Correct 640 ms 150108 KB Output is correct
14 Correct 240 ms 11928 KB Output is correct
15 Correct 508 ms 141932 KB Output is correct
16 Correct 479 ms 142148 KB Output is correct
17 Correct 627 ms 143116 KB Output is correct
18 Correct 527 ms 142912 KB Output is correct
19 Correct 637 ms 146824 KB Output is correct
20 Correct 748 ms 146088 KB Output is correct
21 Correct 503 ms 140476 KB Output is correct
22 Correct 488 ms 141348 KB Output is correct
23 Correct 511 ms 141360 KB Output is correct
24 Correct 513 ms 141584 KB Output is correct
25 Correct 544 ms 143396 KB Output is correct
26 Correct 463 ms 141076 KB Output is correct
27 Correct 435 ms 141092 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 246 ms 11836 KB Output is correct
2 Correct 315 ms 16144 KB Output is correct
3 Correct 249 ms 16340 KB Output is correct
4 Correct 349 ms 16448 KB Output is correct
5 Correct 314 ms 16556 KB Output is correct
6 Correct 254 ms 16232 KB Output is correct
7 Correct 226 ms 11868 KB Output is correct
8 Correct 475 ms 140756 KB Output is correct
9 Correct 468 ms 140708 KB Output is correct
10 Correct 236 ms 12024 KB Output is correct
11 Correct 520 ms 150832 KB Output is correct
12 Correct 518 ms 150752 KB Output is correct
13 Correct 640 ms 150108 KB Output is correct
14 Correct 240 ms 11928 KB Output is correct
15 Correct 508 ms 141932 KB Output is correct
16 Correct 479 ms 142148 KB Output is correct
17 Correct 627 ms 143116 KB Output is correct
18 Correct 527 ms 142912 KB Output is correct
19 Correct 637 ms 146824 KB Output is correct
20 Correct 748 ms 146088 KB Output is correct
21 Correct 503 ms 140476 KB Output is correct
22 Correct 488 ms 141348 KB Output is correct
23 Correct 511 ms 141360 KB Output is correct
24 Correct 513 ms 141584 KB Output is correct
25 Correct 544 ms 143396 KB Output is correct
26 Correct 463 ms 141076 KB Output is correct
27 Correct 435 ms 141092 KB Output is correct
28 Incorrect 240 ms 11696 KB Extra information in the output file
29 Halted 0 ms 0 KB -