oj.uz

Submission #657446

# Submission time Handle Problem Language Result Execution time Memory
657446 2022-11-09T21:02:08 Z Lobo Inside information (BOI21_servers) C++17
15 / 100
 3500 ms 100156 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 maxn = 2e5+10;

int n, k, h[maxn];
int pp[maxn][25], pmn[maxn][25], pmx[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];
    }
    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;
    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:94: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]
   94 |         for(int i = 0; i < ords.size(); i++) {
      |                        ~~^~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 277 ms 9292 KB Output is correct
2 Correct 354 ms 13204 KB Output is correct
3 Correct 287 ms 13096 KB Output is correct
4 Correct 2900 ms 13304 KB Output is correct
5 Correct 3035 ms 13492 KB Output is correct
6 Correct 274 ms 13076 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 277 ms 9292 KB Output is correct
2 Correct 354 ms 13204 KB Output is correct
3 Correct 287 ms 13096 KB Output is correct
4 Correct 2900 ms 13304 KB Output is correct
5 Correct 3035 ms 13492 KB Output is correct
6 Correct 274 ms 13076 KB Output is correct
7 Incorrect 224 ms 9956 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 235 ms 9296 KB Output is correct
2 Correct 421 ms 89084 KB Output is correct
3 Correct 405 ms 89124 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 235 ms 9296 KB Output is correct
2 Correct 421 ms 89084 KB Output is correct
3 Correct 405 ms 89124 KB Output is correct
4 Incorrect 208 ms 9956 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 289 ms 9208 KB Output is correct
2 Correct 458 ms 99996 KB Output is correct
3 Correct 505 ms 99804 KB Output is correct
4 Execution timed out 3592 ms 97796 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 9208 KB Output is correct
2 Correct 458 ms 99996 KB Output is correct
3 Correct 505 ms 99804 KB Output is correct
4 Execution timed out 3592 ms 97796 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 9372 KB Output is correct
2 Correct 619 ms 90700 KB Output is correct
3 Correct 427 ms 90956 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 9372 KB Output is correct
2 Correct 619 ms 90700 KB Output is correct
3 Correct 427 ms 90956 KB Output is correct
4 Incorrect 236 ms 10028 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 278 ms 9240 KB Output is correct
2 Correct 467 ms 100012 KB Output is correct
3 Correct 534 ms 99788 KB Output is correct
4 Execution timed out 3563 ms 97872 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 278 ms 9240 KB Output is correct
2 Correct 467 ms 100012 KB Output is correct
3 Correct 534 ms 99788 KB Output is correct
4 Execution timed out 3563 ms 97872 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 259 ms 9212 KB Output is correct
2 Correct 365 ms 13096 KB Output is correct
3 Correct 282 ms 13104 KB Output is correct
4 Correct 2838 ms 13280 KB Output is correct
5 Correct 3072 ms 13352 KB Output is correct
6 Correct 251 ms 13120 KB Output is correct
7 Correct 235 ms 10260 KB Output is correct
8 Correct 433 ms 89052 KB Output is correct
9 Correct 432 ms 88964 KB Output is correct
10 Correct 304 ms 10152 KB Output is correct
11 Correct 489 ms 100156 KB Output is correct
12 Correct 482 ms 99880 KB Output is correct
13 Execution timed out 3568 ms 97836 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 259 ms 9212 KB Output is correct
2 Correct 365 ms 13096 KB Output is correct
3 Correct 282 ms 13104 KB Output is correct
4 Correct 2838 ms 13280 KB Output is correct
5 Correct 3072 ms 13352 KB Output is correct
6 Correct 251 ms 13120 KB Output is correct
7 Correct 235 ms 10260 KB Output is correct
8 Correct 433 ms 89052 KB Output is correct
9 Correct 432 ms 88964 KB Output is correct
10 Correct 304 ms 10152 KB Output is correct
11 Correct 489 ms 100156 KB Output is correct
12 Correct 482 ms 99880 KB Output is correct
13 Execution timed out 3568 ms 97836 KB Time limit exceeded
14 Halted 0 ms 0 KB -