oj.uz

Submission #657456

# Submission time Handle Problem Language Result Execution time Memory
657456 2022-11-09T21:19:33 Z Lobo Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 145396 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];
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];
        
        }
        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]);


            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));
        }
        else if(op == 'Q') {
            int u,v; cin >> u >> v;
            qrys.pb(mp(mp(0,i),mp(u,v)));
        }
    }

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

    for(auto X : qrys) {
        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(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:124:26: 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]
  124 |         for(int i = 0; i < ords.size(); i++) {
      |                        ~~^~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 235 ms 9280 KB Output is correct
2 Correct 297 ms 13252 KB Output is correct
3 Correct 247 ms 13312 KB Output is correct
4 Correct 1460 ms 13560 KB Output is correct
5 Correct 1525 ms 13828 KB Output is correct
6 Correct 241 ms 13300 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 235 ms 9280 KB Output is correct
2 Correct 297 ms 13252 KB Output is correct
3 Correct 247 ms 13312 KB Output is correct
4 Correct 1460 ms 13560 KB Output is correct
5 Correct 1525 ms 13828 KB Output is correct
6 Correct 241 ms 13300 KB Output is correct
7 Incorrect 220 ms 9228 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 217 ms 9264 KB Output is correct
2 Correct 432 ms 133168 KB Output is correct
3 Correct 453 ms 133144 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 217 ms 9264 KB Output is correct
2 Correct 432 ms 133168 KB Output is correct
3 Correct 453 ms 133144 KB Output is correct
4 Incorrect 207 ms 9224 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 240 ms 9316 KB Output is correct
2 Correct 500 ms 145396 KB Output is correct
3 Correct 512 ms 144596 KB Output is correct
4 Execution timed out 3577 ms 143804 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 9316 KB Output is correct
2 Correct 500 ms 145396 KB Output is correct
3 Correct 512 ms 144596 KB Output is correct
4 Execution timed out 3577 ms 143804 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 9432 KB Output is correct
2 Correct 521 ms 134336 KB Output is correct
3 Correct 438 ms 134680 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 9432 KB Output is correct
2 Correct 521 ms 134336 KB Output is correct
3 Correct 438 ms 134680 KB Output is correct
4 Incorrect 219 ms 9232 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 248 ms 9336 KB Output is correct
2 Correct 522 ms 145392 KB Output is correct
3 Correct 495 ms 144684 KB Output is correct
4 Execution timed out 3599 ms 143816 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 248 ms 9336 KB Output is correct
2 Correct 522 ms 145392 KB Output is correct
3 Correct 495 ms 144684 KB Output is correct
4 Execution timed out 3599 ms 143816 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 238 ms 9308 KB Output is correct
2 Correct 322 ms 13400 KB Output is correct
3 Correct 244 ms 13372 KB Output is correct
4 Correct 1471 ms 13456 KB Output is correct
5 Correct 1512 ms 13840 KB Output is correct
6 Correct 243 ms 13332 KB Output is correct
7 Correct 218 ms 9244 KB Output is correct
8 Correct 460 ms 133276 KB Output is correct
9 Correct 440 ms 133148 KB Output is correct
10 Correct 243 ms 9264 KB Output is correct
11 Correct 499 ms 145296 KB Output is correct
12 Correct 499 ms 144616 KB Output is correct
13 Execution timed out 3587 ms 143904 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 238 ms 9308 KB Output is correct
2 Correct 322 ms 13400 KB Output is correct
3 Correct 244 ms 13372 KB Output is correct
4 Correct 1471 ms 13456 KB Output is correct
5 Correct 1512 ms 13840 KB Output is correct
6 Correct 243 ms 13332 KB Output is correct
7 Correct 218 ms 9244 KB Output is correct
8 Correct 460 ms 133276 KB Output is correct
9 Correct 440 ms 133148 KB Output is correct
10 Correct 243 ms 9264 KB Output is correct
11 Correct 499 ms 145296 KB Output is correct
12 Correct 499 ms 144616 KB Output is correct
13 Execution timed out 3587 ms 143904 KB Time limit exceeded
14 Halted 0 ms 0 KB -