oj.uz

Submission #446875

# Submission time Handle Problem Language Result Execution time Memory
446875 2021-07-23T16:02:54 Z wiwiho Inside information (BOI21_servers) C++14
50 / 100
 385 ms 31528 KB 
#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define F first
#define S second

using namespace std;

typedef long long ll;

using pii = pair<int, int>;

int n, k;
const int SZ = 20;

vector<vector<pii>> g;
vector<int> pw;
vector<vector<int>> anc;
vector<vector<bool>> incr, decr;
vector<int> in, out, dpt;
int ts = 0;

void dfs(int now, int p, int w, int d){
    in[now] = ts++;
    anc[0][now] = p;
    pw[now] = w;
    dpt[now] = d;
    if(pw[now] > pw[p]) incr[0][now] = true;
    else decr[0][now] = true;
    for(pii i : g[now]){
        if(i.F == p) continue;
        dfs(i.F, now, i.S, d + 1);
    }
    out[now] = ts++;
}

void buildAnc(){
    for(int i = 1; i < SZ; i++){
        for(int j = 1; j <= n; j++){
            anc[i][j] = anc[i - 1][anc[i - 1][j]];
            incr[i][j] = incr[i - 1][j] || incr[i - 1][anc[i - 1][j]];
            decr[i][j] = decr[i - 1][j] || decr[i - 1][anc[i - 1][j]];
        }
    }
}

bool isAnc(int a, int b){
    return in[a] <= in[b] && out[a] >= out[b];
}

int lca(int a, int b){
    if(isAnc(a, b)) return a;
    for(int i = SZ - 1; i >= 0; i--){
        if(!isAnc(anc[i][a], b)) a = anc[i][a];
    }
    return anc[0][a];
}

int jump(int a, int len){
    for(int i = 0; i < SZ; i++){
        if(1 << i & len) a = anc[i][a];
    }
    return a;
}

bool checkInc(int a, int len){
    for(int i = 0; i < SZ; i++){
        if(!(1 << i & len)) continue;
        if(incr[i][a]) return false;
        a = anc[i][a];
    }
    return true;
}

bool checkDec(int a, int len){
    for(int i = 0; i < SZ; i++){
        if(!(1 << i & len)) continue;
        if(decr[i][a]) return false;
        a = anc[i][a];
    }
    return true;
}

bool check(int u, int v, int tm){ // u to v increasing
    if(u == v) return true;
    int l = lca(u, v);
    int du = dpt[u] - dpt[l];
    int dv = dpt[v] - dpt[l];
    if(du >= 2){
        if(!checkInc(u, du - 1)) return false;
    }
    if(dv >= 2){
        if(!checkDec(v, dv - 1)) return false;
    }
    if(du > 0 && dv > 0){
        int tu = jump(u, du - 1);
        int tv = jump(v, dv - 1);
        if(pw[tu] > pw[tv]) return false;
    }
    if(dv > 0){
        if(pw[v] > tm) return false;
    }
    else{
        if(pw[jump(u, du - 1)] > tm) return false;
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;

    g.resize(n + 1);
    anc.resize(SZ, vector<int>(n + 1));
    incr.resize(SZ, vector<bool>(n + 1));
    decr.resize(SZ, vector<bool>(n + 1));
    pw.resize(n + 1);
    in.resize(n + 1);
    out.resize(n + 1);
    dpt.resize(n + 1);

    vector<pair<int, pii>> qry;
    for(int i = 0; i < n + k - 1; i++){
        string s;
        cin >> s;
        assert(s != "C");
        if(s == "S"){
            int u, v;
            cin >> u >> v;
            g[u].eb(mp(v, i));
            g[v].eb(mp(u, i));
            continue;
        }
        int v, d;
        cin >> v >> d;
        qry.eb(mp(i, mp(v, d)));
    }

    dfs(1, 1, 0, 0);
    buildAnc();

    for(auto i : qry){
        int tm = i.F;
        int v = i.S.F;
        int d = i.S.S;
        if(check(d, v, tm)) cout << "yes\n";
        else cout << "no\n";
    }

    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2148 KB Output is correct
2 Correct 76 ms 2700 KB Output is correct
3 Correct 82 ms 2844 KB Output is correct
4 Correct 76 ms 2840 KB Output is correct
5 Correct 65 ms 3068 KB Output is correct
6 Correct 89 ms 2788 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2148 KB Output is correct
2 Correct 76 ms 2700 KB Output is correct
3 Correct 82 ms 2844 KB Output is correct
4 Correct 76 ms 2840 KB Output is correct
5 Correct 65 ms 3068 KB Output is correct
6 Correct 89 ms 2788 KB Output is correct
7 Runtime error 2 ms 588 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 2236 KB Output is correct
2 Correct 340 ms 21548 KB Output is correct
3 Correct 321 ms 24388 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 2236 KB Output is correct
2 Correct 340 ms 21548 KB Output is correct
3 Correct 321 ms 24388 KB Output is correct
4 Runtime error 2 ms 716 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2108 KB Output is correct
2 Correct 304 ms 28204 KB Output is correct
3 Correct 245 ms 31440 KB Output is correct
4 Correct 252 ms 31388 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2108 KB Output is correct
2 Correct 304 ms 28204 KB Output is correct
3 Correct 245 ms 31440 KB Output is correct
4 Correct 252 ms 31388 KB Output is correct
5 Runtime error 2 ms 716 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2160 KB Output is correct
2 Correct 263 ms 21560 KB Output is correct
3 Correct 250 ms 25352 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2160 KB Output is correct
2 Correct 263 ms 21560 KB Output is correct
3 Correct 250 ms 25352 KB Output is correct
4 Runtime error 2 ms 716 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2104 KB Output is correct
2 Correct 211 ms 28148 KB Output is correct
3 Correct 227 ms 31468 KB Output is correct
4 Correct 201 ms 31388 KB Output is correct
5 Correct 53 ms 2996 KB Output is correct
6 Correct 284 ms 24840 KB Output is correct
7 Correct 233 ms 25388 KB Output is correct
8 Correct 303 ms 26276 KB Output is correct
9 Correct 303 ms 25712 KB Output is correct
10 Correct 248 ms 29544 KB Output is correct
11 Correct 331 ms 28976 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2104 KB Output is correct
2 Correct 211 ms 28148 KB Output is correct
3 Correct 227 ms 31468 KB Output is correct
4 Correct 201 ms 31388 KB Output is correct
5 Correct 53 ms 2996 KB Output is correct
6 Correct 284 ms 24840 KB Output is correct
7 Correct 233 ms 25388 KB Output is correct
8 Correct 303 ms 26276 KB Output is correct
9 Correct 303 ms 25712 KB Output is correct
10 Correct 248 ms 29544 KB Output is correct
11 Correct 331 ms 28976 KB Output is correct
12 Runtime error 2 ms 716 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2140 KB Output is correct
2 Correct 78 ms 2636 KB Output is correct
3 Correct 87 ms 2816 KB Output is correct
4 Correct 76 ms 2732 KB Output is correct
5 Correct 64 ms 3060 KB Output is correct
6 Correct 98 ms 2712 KB Output is correct
7 Correct 63 ms 2140 KB Output is correct
8 Correct 315 ms 21716 KB Output is correct
9 Correct 343 ms 24396 KB Output is correct
10 Correct 47 ms 3020 KB Output is correct
11 Correct 232 ms 31480 KB Output is correct
12 Correct 253 ms 31528 KB Output is correct
13 Correct 214 ms 31408 KB Output is correct
14 Correct 53 ms 3000 KB Output is correct
15 Correct 255 ms 24800 KB Output is correct
16 Correct 233 ms 25328 KB Output is correct
17 Correct 319 ms 26244 KB Output is correct
18 Correct 258 ms 25704 KB Output is correct
19 Correct 282 ms 29528 KB Output is correct
20 Correct 331 ms 29004 KB Output is correct
21 Correct 385 ms 25016 KB Output is correct
22 Correct 329 ms 25032 KB Output is correct
23 Correct 378 ms 25216 KB Output is correct
24 Correct 355 ms 25320 KB Output is correct
25 Correct 305 ms 26556 KB Output is correct
26 Correct 199 ms 25112 KB Output is correct
27 Correct 171 ms 25528 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2140 KB Output is correct
2 Correct 78 ms 2636 KB Output is correct
3 Correct 87 ms 2816 KB Output is correct
4 Correct 76 ms 2732 KB Output is correct
5 Correct 64 ms 3060 KB Output is correct
6 Correct 98 ms 2712 KB Output is correct
7 Correct 63 ms 2140 KB Output is correct
8 Correct 315 ms 21716 KB Output is correct
9 Correct 343 ms 24396 KB Output is correct
10 Correct 47 ms 3020 KB Output is correct
11 Correct 232 ms 31480 KB Output is correct
12 Correct 253 ms 31528 KB Output is correct
13 Correct 214 ms 31408 KB Output is correct
14 Correct 53 ms 3000 KB Output is correct
15 Correct 255 ms 24800 KB Output is correct
16 Correct 233 ms 25328 KB Output is correct
17 Correct 319 ms 26244 KB Output is correct
18 Correct 258 ms 25704 KB Output is correct
19 Correct 282 ms 29528 KB Output is correct
20 Correct 331 ms 29004 KB Output is correct
21 Correct 385 ms 25016 KB Output is correct
22 Correct 329 ms 25032 KB Output is correct
23 Correct 378 ms 25216 KB Output is correct
24 Correct 355 ms 25320 KB Output is correct
25 Correct 305 ms 26556 KB Output is correct
26 Correct 199 ms 25112 KB Output is correct
27 Correct 171 ms 25528 KB Output is correct
28 Runtime error 2 ms 716 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -