oj.uz

Submission #658022

# Submission time Handle Problem Language Result Execution time Memory
658022 2022-11-11T22:38:51 Z Lobo Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 148800 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 239 ms 9352 KB Output is correct
2 Correct 292 ms 14080 KB Output is correct
3 Correct 256 ms 14124 KB Output is correct
4 Correct 347 ms 14256 KB Output is correct
5 Correct 350 ms 14432 KB Output is correct
6 Correct 254 ms 14128 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 239 ms 9352 KB Output is correct
2 Correct 292 ms 14080 KB Output is correct
3 Correct 256 ms 14124 KB Output is correct
4 Correct 347 ms 14256 KB Output is correct
5 Correct 350 ms 14432 KB Output is correct
6 Correct 254 ms 14128 KB Output is correct
7 Incorrect 233 ms 10040 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 541 ms 138744 KB Output is correct
3 Correct 488 ms 138788 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 541 ms 138744 KB Output is correct
3 Correct 488 ms 138788 KB Output is correct
4 Incorrect 215 ms 10136 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 9324 KB Output is correct
2 Correct 550 ms 148796 KB Output is correct
3 Correct 534 ms 148800 KB Output is correct
4 Execution timed out 3570 ms 148324 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 9324 KB Output is correct
2 Correct 550 ms 148796 KB Output is correct
3 Correct 534 ms 148800 KB Output is correct
4 Execution timed out 3570 ms 148324 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 9264 KB Output is correct
2 Correct 529 ms 140008 KB Output is correct
3 Correct 489 ms 140244 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 9264 KB Output is correct
2 Correct 529 ms 140008 KB Output is correct
3 Correct 489 ms 140244 KB Output is correct
4 Incorrect 225 ms 10032 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 233 ms 9308 KB Output is correct
2 Correct 553 ms 148668 KB Output is correct
3 Correct 538 ms 148644 KB Output is correct
4 Execution timed out 3602 ms 147904 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 233 ms 9308 KB Output is correct
2 Correct 553 ms 148668 KB Output is correct
3 Correct 538 ms 148644 KB Output is correct
4 Execution timed out 3602 ms 147904 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 240 ms 9260 KB Output is correct
2 Correct 293 ms 14024 KB Output is correct
3 Correct 251 ms 14000 KB Output is correct
4 Correct 355 ms 14460 KB Output is correct
5 Correct 323 ms 14312 KB Output is correct
6 Correct 244 ms 14052 KB Output is correct
7 Correct 224 ms 9904 KB Output is correct
8 Correct 496 ms 138600 KB Output is correct
9 Correct 537 ms 138588 KB Output is correct
10 Correct 238 ms 9992 KB Output is correct
11 Correct 546 ms 148636 KB Output is correct
12 Correct 545 ms 148772 KB Output is correct
13 Execution timed out 3514 ms 148124 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 240 ms 9260 KB Output is correct
2 Correct 293 ms 14024 KB Output is correct
3 Correct 251 ms 14000 KB Output is correct
4 Correct 355 ms 14460 KB Output is correct
5 Correct 323 ms 14312 KB Output is correct
6 Correct 244 ms 14052 KB Output is correct
7 Correct 224 ms 9904 KB Output is correct
8 Correct 496 ms 138600 KB Output is correct
9 Correct 537 ms 138588 KB Output is correct
10 Correct 238 ms 9992 KB Output is correct
11 Correct 546 ms 148636 KB Output is correct
12 Correct 545 ms 148772 KB Output is correct
13 Execution timed out 3514 ms 148124 KB Time limit exceeded
14 Halted 0 ms 0 KB -