oj.uz

Submission #657451

# Submission time Handle Problem Language Result Execution time Memory
657451 2022-11-09T21:06:46 Z Lobo Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 122124 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++) {
        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;
        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(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] != 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);

        vector<int> ordu, ordv, ords;
        while(u != lc) {
            ordu.pb(pmn[u][0]);
            u = pp[u][0];
        }

        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);

        string ans = "yes";
        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:104: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]
  104 |         for(int i = 0; i < ords.size(); i++) {
      |                        ~~^~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 247 ms 9296 KB Output is correct
2 Correct 331 ms 12460 KB Output is correct
3 Correct 258 ms 12532 KB Output is correct
4 Correct 2459 ms 12804 KB Output is correct
5 Correct 2784 ms 12928 KB Output is correct
6 Correct 249 ms 12500 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 247 ms 9296 KB Output is correct
2 Correct 331 ms 12460 KB Output is correct
3 Correct 258 ms 12532 KB Output is correct
4 Correct 2459 ms 12804 KB Output is correct
5 Correct 2784 ms 12928 KB Output is correct
6 Correct 249 ms 12500 KB Output is correct
7 Incorrect 227 ms 9148 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 221 ms 9264 KB Output is correct
2 Correct 419 ms 109724 KB Output is correct
3 Correct 440 ms 109704 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 221 ms 9264 KB Output is correct
2 Correct 419 ms 109724 KB Output is correct
3 Correct 440 ms 109704 KB Output is correct
4 Incorrect 204 ms 9156 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 271 ms 9328 KB Output is correct
2 Correct 511 ms 122116 KB Output is correct
3 Correct 513 ms 121984 KB Output is correct
4 Execution timed out 3599 ms 119924 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 9328 KB Output is correct
2 Correct 511 ms 122116 KB Output is correct
3 Correct 513 ms 121984 KB Output is correct
4 Execution timed out 3599 ms 119924 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 9224 KB Output is correct
2 Correct 575 ms 110816 KB Output is correct
3 Correct 432 ms 111132 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 9224 KB Output is correct
2 Correct 575 ms 110816 KB Output is correct
3 Correct 432 ms 111132 KB Output is correct
4 Incorrect 250 ms 9156 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 275 ms 9272 KB Output is correct
2 Correct 529 ms 122064 KB Output is correct
3 Correct 513 ms 122112 KB Output is correct
4 Execution timed out 3593 ms 120132 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 275 ms 9272 KB Output is correct
2 Correct 529 ms 122064 KB Output is correct
3 Correct 513 ms 122112 KB Output is correct
4 Execution timed out 3593 ms 120132 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 268 ms 9292 KB Output is correct
2 Correct 342 ms 12604 KB Output is correct
3 Correct 253 ms 12716 KB Output is correct
4 Correct 2478 ms 12656 KB Output is correct
5 Correct 2783 ms 13052 KB Output is correct
6 Correct 246 ms 12668 KB Output is correct
7 Correct 218 ms 9332 KB Output is correct
8 Correct 416 ms 109724 KB Output is correct
9 Correct 424 ms 109712 KB Output is correct
10 Correct 268 ms 9292 KB Output is correct
11 Correct 504 ms 122124 KB Output is correct
12 Correct 507 ms 121956 KB Output is correct
13 Execution timed out 3573 ms 120172 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 268 ms 9292 KB Output is correct
2 Correct 342 ms 12604 KB Output is correct
3 Correct 253 ms 12716 KB Output is correct
4 Correct 2478 ms 12656 KB Output is correct
5 Correct 2783 ms 13052 KB Output is correct
6 Correct 246 ms 12668 KB Output is correct
7 Correct 218 ms 9332 KB Output is correct
8 Correct 416 ms 109724 KB Output is correct
9 Correct 424 ms 109712 KB Output is correct
10 Correct 268 ms 9292 KB Output is correct
11 Correct 504 ms 122124 KB Output is correct
12 Correct 507 ms 121956 KB Output is correct
13 Execution timed out 3573 ms 120172 KB Time limit exceeded
14 Halted 0 ms 0 KB -