oj.uz

Submission #658019

# Submission time Handle Problem Language Result Execution time Memory
658019 2022-11-11T22:34:23 Z Lobo Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 151356 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 260 ms 9420 KB Output is correct
2 Correct 296 ms 14808 KB Output is correct
3 Correct 259 ms 14884 KB Output is correct
4 Correct 355 ms 15012 KB Output is correct
5 Correct 356 ms 15232 KB Output is correct
6 Correct 268 ms 14832 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 260 ms 9420 KB Output is correct
2 Correct 296 ms 14808 KB Output is correct
3 Correct 259 ms 14884 KB Output is correct
4 Correct 355 ms 15012 KB Output is correct
5 Correct 356 ms 15232 KB Output is correct
6 Correct 268 ms 14832 KB Output is correct
7 Incorrect 238 ms 10164 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 238 ms 9264 KB Output is correct
2 Correct 486 ms 140708 KB Output is correct
3 Correct 515 ms 140740 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 238 ms 9264 KB Output is correct
2 Correct 486 ms 140708 KB Output is correct
3 Correct 515 ms 140740 KB Output is correct
4 Incorrect 230 ms 10220 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 263 ms 9380 KB Output is correct
2 Correct 554 ms 151256 KB Output is correct
3 Correct 554 ms 151212 KB Output is correct
4 Execution timed out 3574 ms 150476 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 9380 KB Output is correct
2 Correct 554 ms 151256 KB Output is correct
3 Correct 554 ms 151212 KB Output is correct
4 Execution timed out 3574 ms 150476 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 9324 KB Output is correct
2 Correct 610 ms 142360 KB Output is correct
3 Correct 498 ms 142632 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 9324 KB Output is correct
2 Correct 610 ms 142360 KB Output is correct
3 Correct 498 ms 142632 KB Output is correct
4 Incorrect 247 ms 10152 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 235 ms 9320 KB Output is correct
2 Correct 576 ms 151356 KB Output is correct
3 Correct 607 ms 151168 KB Output is correct
4 Execution timed out 3602 ms 150140 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 235 ms 9320 KB Output is correct
2 Correct 576 ms 151356 KB Output is correct
3 Correct 607 ms 151168 KB Output is correct
4 Execution timed out 3602 ms 150140 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 245 ms 9316 KB Output is correct
2 Correct 306 ms 14844 KB Output is correct
3 Correct 258 ms 14972 KB Output is correct
4 Correct 344 ms 14904 KB Output is correct
5 Correct 326 ms 15256 KB Output is correct
6 Correct 280 ms 14800 KB Output is correct
7 Correct 243 ms 10236 KB Output is correct
8 Correct 511 ms 140716 KB Output is correct
9 Correct 494 ms 140768 KB Output is correct
10 Correct 243 ms 10140 KB Output is correct
11 Correct 553 ms 151196 KB Output is correct
12 Correct 548 ms 151284 KB Output is correct
13 Execution timed out 3574 ms 150208 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 245 ms 9316 KB Output is correct
2 Correct 306 ms 14844 KB Output is correct
3 Correct 258 ms 14972 KB Output is correct
4 Correct 344 ms 14904 KB Output is correct
5 Correct 326 ms 15256 KB Output is correct
6 Correct 280 ms 14800 KB Output is correct
7 Correct 243 ms 10236 KB Output is correct
8 Correct 511 ms 140716 KB Output is correct
9 Correct 494 ms 140768 KB Output is correct
10 Correct 243 ms 10140 KB Output is correct
11 Correct 553 ms 151196 KB Output is correct
12 Correct 548 ms 151284 KB Output is correct
13 Execution timed out 3574 ms 150208 KB Time limit exceeded
14 Halted 0 ms 0 KB -