oj.uz

Submission #554453

# Submission time Handle Problem Language Result Execution time Memory
554453 2022-04-28T12:29:40 Z Jarif_Rahman Inside information (BOI21_servers) C++17
50 / 100
 679 ms 36872 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;

struct BIT{
    int n;
    vector<ll> sm;
    BIT(int _n){
        n = _n;
        sm.resize(n);
    }
    void add(int in, ll x){
        in++;
        while(in <= n) sm[in-1]+=x, in+=in&-in;
    }
    ll sum(int in){
        in++;
        ll s = 0;
        while(in >= 1) s+=sm[in-1], in-=in&-in;
        return s;
    }
    ll sum(int l, int r){
        return sum(r)-(l == 0? 0:sum(l-1));
    }
};

BIT bit(0);

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

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

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]);

    if(isInc){
        sth.pb({_mn, _mx});
        bit.add(_mx+1, 1);
    }

    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) 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]] = "yes";
    }
    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]) dfs2(x, nd);
}

void dfs3(int nd, int ss){
    for(auto [in, d]: queires[nd]){
        if(d != -1) continue;
        if(!isdec[nd]) continue;
        ans[qa[in]] = to_string(stoi(ans[qa[in]])+bit.sum(0, in));
    }
    if(ss != -1){
        for(auto [x, w]: v[nd]) if(x != ss && !marked[x]) dfs3(x, nd);
        return;
    }

    int I = 0;
    vector<pair<int, int>> s;

    for(auto [x, w]: v[nd]) if(x != ss && !marked[x]) s.pb({w, x});

    sort(s.begin(), s.end());
    
    for(int i = 0; i < s.size(); i++){
        while(I < sth.size() && sth[I].f <= s[i].f){
            bit.add(sth[I].sc+1, -1);
            I++;
        }
        dfs3(s[i].sc, nd);
    }
    while(I < sth.size()){
        bit.add(sth[I].sc+1, -1);
        I++;
    }
}

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);

    bit = BIT(q+2);

    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 ? "yes":"no");
        }
        else{
            queires[a].pb({i, -1});
            qa[i] = ans.size();
            ans.pb("0");
        }
    }

    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);

        sort(sth.begin(), sth.end());
        dfs3(c, -1);

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

    for(auto x: ans) cout << x << "\n";
}

Compilation message

servers.cpp: In function 'void dfs3(int, int)':
servers.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
servers.cpp:119:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         while(I < sth.size() && sth[I].f <= s[i].f){
      |               ~~^~~~~~~~~~~~
servers.cpp:125:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     while(I < sth.size()){
      |           ~~^~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7836 KB Output is correct
2 Correct 49 ms 8588 KB Output is correct
3 Correct 42 ms 8468 KB Output is correct
4 Correct 50 ms 8884 KB Output is correct
5 Correct 51 ms 9092 KB Output is correct
6 Correct 47 ms 8796 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7836 KB Output is correct
2 Correct 49 ms 8588 KB Output is correct
3 Correct 42 ms 8468 KB Output is correct
4 Correct 50 ms 8884 KB Output is correct
5 Correct 51 ms 9092 KB Output is correct
6 Correct 47 ms 8796 KB Output is correct
7 Incorrect 35 ms 7884 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 30 ms 7784 KB Output is correct
2 Correct 197 ms 25572 KB Output is correct
3 Correct 197 ms 25760 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7784 KB Output is correct
2 Correct 197 ms 25572 KB Output is correct
3 Correct 197 ms 25760 KB Output is correct
4 Incorrect 30 ms 7912 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 30 ms 7980 KB Output is correct
2 Correct 634 ms 35676 KB Output is correct
3 Correct 584 ms 35628 KB Output is correct
4 Correct 371 ms 35848 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7980 KB Output is correct
2 Correct 634 ms 35676 KB Output is correct
3 Correct 584 ms 35628 KB Output is correct
4 Correct 371 ms 35848 KB Output is correct
5 Incorrect 32 ms 7784 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 31 ms 7996 KB Output is correct
2 Correct 394 ms 23832 KB Output is correct
3 Correct 490 ms 23168 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7996 KB Output is correct
2 Correct 394 ms 23832 KB Output is correct
3 Correct 490 ms 23168 KB Output is correct
4 Incorrect 33 ms 7816 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 31 ms 8092 KB Output is correct
2 Correct 639 ms 35768 KB Output is correct
3 Correct 591 ms 35600 KB Output is correct
4 Correct 389 ms 35840 KB Output is correct
5 Correct 30 ms 7752 KB Output is correct
6 Correct 376 ms 23788 KB Output is correct
7 Correct 475 ms 23180 KB Output is correct
8 Correct 532 ms 23988 KB Output is correct
9 Correct 573 ms 23668 KB Output is correct
10 Correct 657 ms 30728 KB Output is correct
11 Correct 624 ms 30036 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8092 KB Output is correct
2 Correct 639 ms 35768 KB Output is correct
3 Correct 591 ms 35600 KB Output is correct
4 Correct 389 ms 35840 KB Output is correct
5 Correct 30 ms 7752 KB Output is correct
6 Correct 376 ms 23788 KB Output is correct
7 Correct 475 ms 23180 KB Output is correct
8 Correct 532 ms 23988 KB Output is correct
9 Correct 573 ms 23668 KB Output is correct
10 Correct 657 ms 30728 KB Output is correct
11 Correct 624 ms 30036 KB Output is correct
12 Incorrect 30 ms 7784 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 31 ms 8056 KB Output is correct
2 Correct 46 ms 8668 KB Output is correct
3 Correct 44 ms 8464 KB Output is correct
4 Correct 59 ms 8836 KB Output is correct
5 Correct 56 ms 9164 KB Output is correct
6 Correct 43 ms 8856 KB Output is correct
7 Correct 29 ms 8092 KB Output is correct
8 Correct 184 ms 25496 KB Output is correct
9 Correct 193 ms 25524 KB Output is correct
10 Correct 32 ms 7788 KB Output is correct
11 Correct 577 ms 35272 KB Output is correct
12 Correct 590 ms 35292 KB Output is correct
13 Correct 395 ms 36000 KB Output is correct
14 Correct 29 ms 7788 KB Output is correct
15 Correct 364 ms 23828 KB Output is correct
16 Correct 528 ms 23068 KB Output is correct
17 Correct 612 ms 23768 KB Output is correct
18 Correct 584 ms 23672 KB Output is correct
19 Correct 645 ms 30568 KB Output is correct
20 Correct 656 ms 30060 KB Output is correct
21 Correct 227 ms 24868 KB Output is correct
22 Correct 234 ms 24264 KB Output is correct
23 Correct 353 ms 23272 KB Output is correct
24 Correct 378 ms 23256 KB Output is correct
25 Correct 679 ms 36872 KB Output is correct
26 Correct 508 ms 22084 KB Output is correct
27 Correct 436 ms 21948 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8056 KB Output is correct
2 Correct 46 ms 8668 KB Output is correct
3 Correct 44 ms 8464 KB Output is correct
4 Correct 59 ms 8836 KB Output is correct
5 Correct 56 ms 9164 KB Output is correct
6 Correct 43 ms 8856 KB Output is correct
7 Correct 29 ms 8092 KB Output is correct
8 Correct 184 ms 25496 KB Output is correct
9 Correct 193 ms 25524 KB Output is correct
10 Correct 32 ms 7788 KB Output is correct
11 Correct 577 ms 35272 KB Output is correct
12 Correct 590 ms 35292 KB Output is correct
13 Correct 395 ms 36000 KB Output is correct
14 Correct 29 ms 7788 KB Output is correct
15 Correct 364 ms 23828 KB Output is correct
16 Correct 528 ms 23068 KB Output is correct
17 Correct 612 ms 23768 KB Output is correct
18 Correct 584 ms 23672 KB Output is correct
19 Correct 645 ms 30568 KB Output is correct
20 Correct 656 ms 30060 KB Output is correct
21 Correct 227 ms 24868 KB Output is correct
22 Correct 234 ms 24264 KB Output is correct
23 Correct 353 ms 23272 KB Output is correct
24 Correct 378 ms 23256 KB Output is correct
25 Correct 679 ms 36872 KB Output is correct
26 Correct 508 ms 22084 KB Output is correct
27 Correct 436 ms 21948 KB Output is correct
28 Incorrect 31 ms 7772 KB Extra information in the output file
29 Halted 0 ms 0 KB -