Submission #554711

#	Time	Username	Problem	Language	Result	Execution time	Memory
554711		Jarif_Rahman	Inside information (BOI21_servers)	C++17	100 / 100	1054 ms	39816 KiB

servers

#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 (stderr)

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
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5