oj.uz

Submission #554426

# Submission time Handle Problem Language Result Execution time Memory
554426 2022-04-28T11:29:20 Z Jarif_Rahman Inside information (BOI21_servers) C++17
50 / 100
 578 ms 24028 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] = q+1;
    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(d == -1){
            if(!isdec[nd]) continue;
            continue;
        }
        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, q+1);
    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;;
        if(tt != 'C') cin >> b;
        a--, b--;
        if(tt == 'S'){
            v[a].pb({b, i});
            v[b].pb({a, i});
        }
        else if(tt == 'Q'){
            queires[a].pb({i, b});
            qa[i] = ans.size();
            ans.pb(a == b);
        }
        else{
            queires[a].pb({i, -1});
        }
    }

    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, q+1, 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 20 ms 2764 KB Output is correct
2 Correct 35 ms 3168 KB Output is correct
3 Correct 31 ms 3024 KB Output is correct
4 Correct 39 ms 3268 KB Output is correct
5 Correct 39 ms 3456 KB Output is correct
6 Correct 31 ms 3216 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2764 KB Output is correct
2 Correct 35 ms 3168 KB Output is correct
3 Correct 31 ms 3024 KB Output is correct
4 Correct 39 ms 3268 KB Output is correct
5 Correct 39 ms 3456 KB Output is correct
6 Correct 31 ms 3216 KB Output is correct
7 Incorrect 25 ms 3324 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 22 ms 2764 KB Output is correct
2 Correct 156 ms 17172 KB Output is correct
3 Correct 163 ms 17148 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 156 ms 17172 KB Output is correct
3 Correct 163 ms 17148 KB Output is correct
4 Incorrect 25 ms 3452 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2704 KB Output is correct
2 Correct 502 ms 23636 KB Output is correct
3 Correct 446 ms 23728 KB Output is correct
4 Correct 246 ms 23372 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2704 KB Output is correct
2 Correct 502 ms 23636 KB Output is correct
3 Correct 446 ms 23728 KB Output is correct
4 Correct 246 ms 23372 KB Output is correct
5 Incorrect 20 ms 3332 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2784 KB Output is correct
2 Correct 265 ms 17136 KB Output is correct
3 Correct 359 ms 17100 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2784 KB Output is correct
2 Correct 265 ms 17136 KB Output is correct
3 Correct 359 ms 17100 KB Output is correct
4 Incorrect 24 ms 3396 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2820 KB Output is correct
2 Correct 447 ms 23620 KB Output is correct
3 Correct 468 ms 23664 KB Output is correct
4 Correct 252 ms 23468 KB Output is correct
5 Correct 19 ms 2796 KB Output is correct
6 Correct 243 ms 17124 KB Output is correct
7 Correct 353 ms 17128 KB Output is correct
8 Correct 402 ms 17832 KB Output is correct
9 Correct 442 ms 17668 KB Output is correct
10 Correct 511 ms 21724 KB Output is correct
11 Correct 469 ms 21160 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2820 KB Output is correct
2 Correct 447 ms 23620 KB Output is correct
3 Correct 468 ms 23664 KB Output is correct
4 Correct 252 ms 23468 KB Output is correct
5 Correct 19 ms 2796 KB Output is correct
6 Correct 243 ms 17124 KB Output is correct
7 Correct 353 ms 17128 KB Output is correct
8 Correct 402 ms 17832 KB Output is correct
9 Correct 442 ms 17668 KB Output is correct
10 Correct 511 ms 21724 KB Output is correct
11 Correct 469 ms 21160 KB Output is correct
12 Incorrect 21 ms 3412 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2820 KB Output is correct
2 Correct 33 ms 3136 KB Output is correct
3 Correct 32 ms 3072 KB Output is correct
4 Correct 34 ms 3248 KB Output is correct
5 Correct 35 ms 3532 KB Output is correct
6 Correct 28 ms 3240 KB Output is correct
7 Correct 21 ms 2764 KB Output is correct
8 Correct 134 ms 17156 KB Output is correct
9 Correct 129 ms 17160 KB Output is correct
10 Correct 19 ms 2764 KB Output is correct
11 Correct 431 ms 23720 KB Output is correct
12 Correct 480 ms 23632 KB Output is correct
13 Correct 279 ms 23388 KB Output is correct
14 Correct 31 ms 2684 KB Output is correct
15 Correct 302 ms 17100 KB Output is correct
16 Correct 468 ms 17116 KB Output is correct
17 Correct 501 ms 17776 KB Output is correct
18 Correct 537 ms 17668 KB Output is correct
19 Correct 570 ms 21732 KB Output is correct
20 Correct 578 ms 21032 KB Output is correct
21 Correct 214 ms 17080 KB Output is correct
22 Correct 194 ms 17028 KB Output is correct
23 Correct 340 ms 17244 KB Output is correct
24 Correct 320 ms 17272 KB Output is correct
25 Correct 577 ms 24028 KB Output is correct
26 Correct 411 ms 16024 KB Output is correct
27 Correct 461 ms 16024 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2820 KB Output is correct
2 Correct 33 ms 3136 KB Output is correct
3 Correct 32 ms 3072 KB Output is correct
4 Correct 34 ms 3248 KB Output is correct
5 Correct 35 ms 3532 KB Output is correct
6 Correct 28 ms 3240 KB Output is correct
7 Correct 21 ms 2764 KB Output is correct
8 Correct 134 ms 17156 KB Output is correct
9 Correct 129 ms 17160 KB Output is correct
10 Correct 19 ms 2764 KB Output is correct
11 Correct 431 ms 23720 KB Output is correct
12 Correct 480 ms 23632 KB Output is correct
13 Correct 279 ms 23388 KB Output is correct
14 Correct 31 ms 2684 KB Output is correct
15 Correct 302 ms 17100 KB Output is correct
16 Correct 468 ms 17116 KB Output is correct
17 Correct 501 ms 17776 KB Output is correct
18 Correct 537 ms 17668 KB Output is correct
19 Correct 570 ms 21732 KB Output is correct
20 Correct 578 ms 21032 KB Output is correct
21 Correct 214 ms 17080 KB Output is correct
22 Correct 194 ms 17028 KB Output is correct
23 Correct 340 ms 17244 KB Output is correct
24 Correct 320 ms 17272 KB Output is correct
25 Correct 577 ms 24028 KB Output is correct
26 Correct 411 ms 16024 KB Output is correct
27 Correct 461 ms 16024 KB Output is correct
28 Incorrect 32 ms 3324 KB Extra information in the output file
29 Halted 0 ms 0 KB -