oj.uz

Submission #554711

# Submission time Handle Problem Language Result Execution time Memory
554711 2022-04-29T08:57:00 Z Jarif_Rahman Inside information (BOI21_servers) C++17
100 / 100
 1054 ms 39816 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;
        if(in <= mx[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:119: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]
  119 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
servers.cpp:120: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]
  120 |         while(I < sth.size() && sth[I].f <= s[i].f){
      |               ~~^~~~~~~~~~~~
servers.cpp:126: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]
  126 |     while(I < sth.size()){
      |           ~~^~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8384 KB Output is correct
2 Correct 52 ms 9260 KB Output is correct
3 Correct 43 ms 9120 KB Output is correct
4 Correct 54 ms 9512 KB Output is correct
5 Correct 52 ms 9776 KB Output is correct
6 Correct 44 ms 9388 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8384 KB Output is correct
2 Correct 52 ms 9260 KB Output is correct
3 Correct 43 ms 9120 KB Output is correct
4 Correct 54 ms 9512 KB Output is correct
5 Correct 52 ms 9776 KB Output is correct
6 Correct 44 ms 9388 KB Output is correct
7 Correct 31 ms 8236 KB Output is correct
8 Correct 60 ms 8948 KB Output is correct
9 Correct 44 ms 8732 KB Output is correct
10 Correct 70 ms 9184 KB Output is correct
11 Correct 71 ms 9464 KB Output is correct
12 Correct 44 ms 8976 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8392 KB Output is correct
2 Correct 207 ms 28108 KB Output is correct
3 Correct 184 ms 27964 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8392 KB Output is correct
2 Correct 207 ms 28108 KB Output is correct
3 Correct 184 ms 27964 KB Output is correct
4 Correct 30 ms 8252 KB Output is correct
5 Correct 199 ms 27808 KB Output is correct
6 Correct 112 ms 25828 KB Output is correct
7 Correct 125 ms 26036 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8272 KB Output is correct
2 Correct 607 ms 38184 KB Output is correct
3 Correct 607 ms 38212 KB Output is correct
4 Correct 376 ms 38796 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8272 KB Output is correct
2 Correct 607 ms 38184 KB Output is correct
3 Correct 607 ms 38212 KB Output is correct
4 Correct 376 ms 38796 KB Output is correct
5 Correct 30 ms 8196 KB Output is correct
6 Correct 645 ms 37812 KB Output is correct
7 Correct 478 ms 38556 KB Output is correct
8 Correct 639 ms 37548 KB Output is correct
9 Correct 629 ms 37408 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8300 KB Output is correct
2 Correct 391 ms 26720 KB Output is correct
3 Correct 499 ms 26016 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8300 KB Output is correct
2 Correct 391 ms 26720 KB Output is correct
3 Correct 499 ms 26016 KB Output is correct
4 Correct 30 ms 8124 KB Output is correct
5 Correct 526 ms 26440 KB Output is correct
6 Correct 559 ms 25856 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8284 KB Output is correct
2 Correct 620 ms 38192 KB Output is correct
3 Correct 598 ms 38196 KB Output is correct
4 Correct 377 ms 38708 KB Output is correct
5 Correct 31 ms 8296 KB Output is correct
6 Correct 371 ms 26680 KB Output is correct
7 Correct 492 ms 26020 KB Output is correct
8 Correct 554 ms 26812 KB Output is correct
9 Correct 573 ms 26576 KB Output is correct
10 Correct 695 ms 33728 KB Output is correct
11 Correct 681 ms 33024 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 8284 KB Output is correct
2 Correct 620 ms 38192 KB Output is correct
3 Correct 598 ms 38196 KB Output is correct
4 Correct 377 ms 38708 KB Output is correct
5 Correct 31 ms 8296 KB Output is correct
6 Correct 371 ms 26680 KB Output is correct
7 Correct 492 ms 26020 KB Output is correct
8 Correct 554 ms 26812 KB Output is correct
9 Correct 573 ms 26576 KB Output is correct
10 Correct 695 ms 33728 KB Output is correct
11 Correct 681 ms 33024 KB Output is correct
12 Correct 31 ms 8196 KB Output is correct
13 Correct 675 ms 37800 KB Output is correct
14 Correct 494 ms 38580 KB Output is correct
15 Correct 604 ms 37424 KB Output is correct
16 Correct 634 ms 37408 KB Output is correct
17 Correct 30 ms 8172 KB Output is correct
18 Correct 498 ms 26420 KB Output is correct
19 Correct 554 ms 25764 KB Output is correct
20 Correct 608 ms 26248 KB Output is correct
21 Correct 631 ms 26400 KB Output is correct
22 Correct 744 ms 33016 KB Output is correct
23 Correct 1022 ms 32592 KB Output is correct
24 Correct 846 ms 32988 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8364 KB Output is correct
2 Correct 46 ms 9288 KB Output is correct
3 Correct 45 ms 9236 KB Output is correct
4 Correct 49 ms 9492 KB Output is correct
5 Correct 52 ms 9716 KB Output is correct
6 Correct 46 ms 9388 KB Output is correct
7 Correct 29 ms 8288 KB Output is correct
8 Correct 190 ms 28020 KB Output is correct
9 Correct 195 ms 28056 KB Output is correct
10 Correct 28 ms 8308 KB Output is correct
11 Correct 621 ms 38140 KB Output is correct
12 Correct 599 ms 38220 KB Output is correct
13 Correct 364 ms 38824 KB Output is correct
14 Correct 34 ms 8308 KB Output is correct
15 Correct 379 ms 26796 KB Output is correct
16 Correct 481 ms 26036 KB Output is correct
17 Correct 545 ms 26704 KB Output is correct
18 Correct 567 ms 26548 KB Output is correct
19 Correct 675 ms 33716 KB Output is correct
20 Correct 648 ms 33020 KB Output is correct
21 Correct 229 ms 27928 KB Output is correct
22 Correct 225 ms 27244 KB Output is correct
23 Correct 373 ms 26216 KB Output is correct
24 Correct 359 ms 26156 KB Output is correct
25 Correct 662 ms 39816 KB Output is correct
26 Correct 506 ms 25012 KB Output is correct
27 Correct 527 ms 24988 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8364 KB Output is correct
2 Correct 46 ms 9288 KB Output is correct
3 Correct 45 ms 9236 KB Output is correct
4 Correct 49 ms 9492 KB Output is correct
5 Correct 52 ms 9716 KB Output is correct
6 Correct 46 ms 9388 KB Output is correct
7 Correct 29 ms 8288 KB Output is correct
8 Correct 190 ms 28020 KB Output is correct
9 Correct 195 ms 28056 KB Output is correct
10 Correct 28 ms 8308 KB Output is correct
11 Correct 621 ms 38140 KB Output is correct
12 Correct 599 ms 38220 KB Output is correct
13 Correct 364 ms 38824 KB Output is correct
14 Correct 34 ms 8308 KB Output is correct
15 Correct 379 ms 26796 KB Output is correct
16 Correct 481 ms 26036 KB Output is correct
17 Correct 545 ms 26704 KB Output is correct
18 Correct 567 ms 26548 KB Output is correct
19 Correct 675 ms 33716 KB Output is correct
20 Correct 648 ms 33020 KB Output is correct
21 Correct 229 ms 27928 KB Output is correct
22 Correct 225 ms 27244 KB Output is correct
23 Correct 373 ms 26216 KB Output is correct
24 Correct 359 ms 26156 KB Output is correct
25 Correct 662 ms 39816 KB Output is correct
26 Correct 506 ms 25012 KB Output is correct
27 Correct 527 ms 24988 KB Output is correct
28 Correct 31 ms 8180 KB Output is correct
29 Correct 60 ms 8992 KB Output is correct
30 Correct 52 ms 8772 KB Output is correct
31 Correct 68 ms 9176 KB Output is correct
32 Correct 77 ms 9404 KB Output is correct
33 Correct 47 ms 9004 KB Output is correct
34 Correct 34 ms 8232 KB Output is correct
35 Correct 184 ms 27820 KB Output is correct
36 Correct 126 ms 25880 KB Output is correct
37 Correct 126 ms 26200 KB Output is correct
38 Correct 33 ms 8300 KB Output is correct
39 Correct 625 ms 37820 KB Output is correct
40 Correct 505 ms 38560 KB Output is correct
41 Correct 626 ms 37440 KB Output is correct
42 Correct 610 ms 37592 KB Output is correct
43 Correct 29 ms 8224 KB Output is correct
44 Correct 509 ms 26412 KB Output is correct
45 Correct 545 ms 25748 KB Output is correct
46 Correct 638 ms 26296 KB Output is correct
47 Correct 623 ms 26388 KB Output is correct
48 Correct 743 ms 33144 KB Output is correct
49 Correct 1054 ms 32552 KB Output is correct
50 Correct 933 ms 33004 KB Output is correct
51 Correct 159 ms 26772 KB Output is correct
52 Correct 137 ms 26868 KB Output is correct
53 Correct 127 ms 26344 KB Output is correct
54 Correct 139 ms 27064 KB Output is correct
55 Correct 134 ms 25652 KB Output is correct
56 Correct 341 ms 25524 KB Output is correct
57 Correct 537 ms 37924 KB Output is correct
58 Correct 718 ms 25172 KB Output is correct
59 Correct 492 ms 25220 KB Output is correct