oj.uz

Submission #554423

# Submission time Handle Problem Language Result Execution time Memory
554423 2022-04-28T11:20:03 Z Jarif_Rahman Inside information (BOI21_servers) C++17
50 / 100
 663 ms 27408 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, q;
vector<vector<pair<int, int>>> v;
vector<int> sz;
vector<vector<pair<int, int>>> queires;
vector<bool> marked, ans;
vector<int> qa;

vector<bool> isdec, isinc;
vector<int> mx, mn;
vector<int> centroid_id, anc_id;

void pre_centroid(int nd, int ss){
    sz[nd] = 1;
    isdec[nd] = 1;
    isinc[nd] = 1;
    mx[nd] = -1;
    mn[nd] = 1e9;
    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]) pre_centroid(x, nd);
    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]) sz[nd]+=sz[x];
}

int centroid(int nd, int ss, int total){
    int mx = 0;
    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]) mx = max(mx, sz[x]);
    if(mx <= total/2 && total-sz[nd] <= total/2) return nd;
    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]){
        int cur = centroid(x, nd, total);
        if(cur != -1) return cur;
    }
    return -1;
}

void dfs1(int nd, int ss, int anc, int _mx, int _mn, bool isDec, bool isInc){
    isdec[nd] = isDec;
    isinc[nd] = isInc;
    mx[nd] = _mx;
    mn[nd] = _mn;
    anc_id[nd] = anc;

    centroid_id[nd] = (ss == -1?nd:centroid_id[ss]);

    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]){
        dfs1(x, nd, anc==-1?x:anc, max(_mx, w), min(_mn, w), isDec & (w < _mn), isInc & (w > _mx));
    }
}

void dfs2(int nd, int ss){
    for(auto [in, d]: queires[nd]){
        if(centroid_id[d] != centroid_id[nd]) continue;
        if(anc_id[nd] == anc_id[d]) continue;
        if(in <= max(mx[d], mx[nd])) continue;
        if(!isdec[d]) continue;
        if(!isinc[nd]) continue;
        if(mx[d] >= mn[nd]) continue;
        ans[qa[in]] = 1;
    }
    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]) dfs2(x, nd);
}

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

    cin >> n >> q; q+=n-1;

    v.assign(n, {});
    sz.assign(n, 1);
    queires.assign(n, {});
    marked.assign(n, 0);
    qa.assign(q, -1);

    isdec.assign(n, 1);
    isinc.assign(n, 1);
    mx.assign(n, -1);
    mn.assign(n, 1e9);
    centroid_id.assign(n, -1);
    anc_id.assign(n, -1);

    for(int i = 0; i < q; i++){
        char tt; int a, b; cin >> tt >> a >> b; a--, b--;
        if(tt == 'S'){
            v[a].pb({b, i});
            v[b].pb({a, i});
        }
        else{
            queires[a].pb({i, b});
            qa[i] = ans.size();
            ans.pb(a == b);
        }
    }

    queue<int> Q;
    Q.push(0);

    while(!Q.empty()){
        int x = Q.front();
        Q.pop();
        pre_centroid(x, -1);
        int c = centroid(x, -1, sz[x]);

        dfs1(c, -1, -1, -1, 1e9, 1, 1);
        dfs2(c, -1);

        marked[c] = 1;
        for(auto [x, w]: v[c]) if(!marked[x]) Q.push(x);
    }

    for(auto bl: ans) cout << (bl?"yes\n":"no\n");
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2772 KB Output is correct
2 Correct 39 ms 4236 KB Output is correct
3 Correct 38 ms 4096 KB Output is correct
4 Correct 41 ms 4316 KB Output is correct
5 Correct 38 ms 4464 KB Output is correct
6 Correct 40 ms 4264 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2772 KB Output is correct
2 Correct 39 ms 4236 KB Output is correct
3 Correct 38 ms 4096 KB Output is correct
4 Correct 41 ms 4316 KB Output is correct
5 Correct 38 ms 4464 KB Output is correct
6 Correct 40 ms 4264 KB Output is correct
7 Runtime error 2 ms 1492 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2764 KB Output is correct
2 Correct 178 ms 20140 KB Output is correct
3 Correct 137 ms 20008 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2764 KB Output is correct
2 Correct 178 ms 20140 KB Output is correct
3 Correct 137 ms 20008 KB Output is correct
4 Runtime error 2 ms 1492 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2772 KB Output is correct
2 Correct 501 ms 24368 KB Output is correct
3 Correct 564 ms 24432 KB Output is correct
4 Correct 273 ms 26828 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2772 KB Output is correct
2 Correct 501 ms 24368 KB Output is correct
3 Correct 564 ms 24432 KB Output is correct
4 Correct 273 ms 26828 KB Output is correct
5 Runtime error 2 ms 1492 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2772 KB Output is correct
2 Correct 283 ms 20404 KB Output is correct
3 Correct 464 ms 20384 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2772 KB Output is correct
2 Correct 283 ms 20404 KB Output is correct
3 Correct 464 ms 20384 KB Output is correct
4 Runtime error 2 ms 1608 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2780 KB Output is correct
2 Correct 552 ms 24280 KB Output is correct
3 Correct 491 ms 24288 KB Output is correct
4 Correct 267 ms 26696 KB Output is correct
5 Correct 25 ms 3648 KB Output is correct
6 Correct 265 ms 20404 KB Output is correct
7 Correct 383 ms 20388 KB Output is correct
8 Correct 482 ms 21136 KB Output is correct
9 Correct 510 ms 20976 KB Output is correct
10 Correct 540 ms 25088 KB Output is correct
11 Correct 663 ms 24328 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2780 KB Output is correct
2 Correct 552 ms 24280 KB Output is correct
3 Correct 491 ms 24288 KB Output is correct
4 Correct 267 ms 26696 KB Output is correct
5 Correct 25 ms 3648 KB Output is correct
6 Correct 265 ms 20404 KB Output is correct
7 Correct 383 ms 20388 KB Output is correct
8 Correct 482 ms 21136 KB Output is correct
9 Correct 510 ms 20976 KB Output is correct
10 Correct 540 ms 25088 KB Output is correct
11 Correct 663 ms 24328 KB Output is correct
12 Runtime error 2 ms 1572 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2820 KB Output is correct
2 Correct 37 ms 3796 KB Output is correct
3 Correct 34 ms 3664 KB Output is correct
4 Correct 42 ms 3996 KB Output is correct
5 Correct 50 ms 4072 KB Output is correct
6 Correct 31 ms 3948 KB Output is correct
7 Correct 24 ms 3356 KB Output is correct
8 Correct 136 ms 19956 KB Output is correct
9 Correct 157 ms 20032 KB Output is correct
10 Correct 21 ms 3632 KB Output is correct
11 Correct 459 ms 26912 KB Output is correct
12 Correct 520 ms 26920 KB Output is correct
13 Correct 253 ms 26872 KB Output is correct
14 Correct 23 ms 3660 KB Output is correct
15 Correct 276 ms 20460 KB Output is correct
16 Correct 391 ms 20372 KB Output is correct
17 Correct 407 ms 21032 KB Output is correct
18 Correct 426 ms 20944 KB Output is correct
19 Correct 499 ms 25036 KB Output is correct
20 Correct 488 ms 24372 KB Output is correct
21 Correct 154 ms 20536 KB Output is correct
22 Correct 176 ms 20524 KB Output is correct
23 Correct 258 ms 20428 KB Output is correct
24 Correct 287 ms 20576 KB Output is correct
25 Correct 529 ms 27408 KB Output is correct
26 Correct 414 ms 19532 KB Output is correct
27 Correct 343 ms 19388 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2820 KB Output is correct
2 Correct 37 ms 3796 KB Output is correct
3 Correct 34 ms 3664 KB Output is correct
4 Correct 42 ms 3996 KB Output is correct
5 Correct 50 ms 4072 KB Output is correct
6 Correct 31 ms 3948 KB Output is correct
7 Correct 24 ms 3356 KB Output is correct
8 Correct 136 ms 19956 KB Output is correct
9 Correct 157 ms 20032 KB Output is correct
10 Correct 21 ms 3632 KB Output is correct
11 Correct 459 ms 26912 KB Output is correct
12 Correct 520 ms 26920 KB Output is correct
13 Correct 253 ms 26872 KB Output is correct
14 Correct 23 ms 3660 KB Output is correct
15 Correct 276 ms 20460 KB Output is correct
16 Correct 391 ms 20372 KB Output is correct
17 Correct 407 ms 21032 KB Output is correct
18 Correct 426 ms 20944 KB Output is correct
19 Correct 499 ms 25036 KB Output is correct
20 Correct 488 ms 24372 KB Output is correct
21 Correct 154 ms 20536 KB Output is correct
22 Correct 176 ms 20524 KB Output is correct
23 Correct 258 ms 20428 KB Output is correct
24 Correct 287 ms 20576 KB Output is correct
25 Correct 529 ms 27408 KB Output is correct
26 Correct 414 ms 19532 KB Output is correct
27 Correct 343 ms 19388 KB Output is correct
28 Runtime error 2 ms 1492 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -