oj.uz

Submission #554394

# Submission time Handle Problem Language Result Execution time Memory
554394 2022-04-28T10:38:21 Z Jarif_Rahman Inside information (BOI21_servers) C++17
0 / 100
 23 ms 3668 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;
    centroid_id[nd] = (ss == -1?nd:centroid_id[ss]);
    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;

    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 <= min(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
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 3660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 3660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 3668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 3668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 3532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 3532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 3576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 3576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 3428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 3428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3340 KB Output isn't correct
2 Halted 0 ms 0 KB -