Submission #524351

#	Time	Username	Problem	Language	Result	Execution time	Memory
524351		IMystic	Ball Machine (BOI13_ballmachine)	C++17	8.57 / 100	121 ms	44016 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100010, INF = 1000000000;
vector<int> adj[N];
vector<int> pref(N, INF), dist(N, INF);
vector<int> order, lca;

void dfs(int n, int par){
    sort(adj[n].begin(), adj[n].end(), [](int a, int b){return pref[a] < pref[b];});
    if(par != -1)dist[n] = dist[par] + 1;
    for(int c : adj[n]){
        if(c != par){
            dfs(c, n);
        }
    }
    order.push_back(n);
}



template <class S> 
struct segment {
public :

    explicit segment(int _n) : n(_n) {
        log = 1;
        while((1<<log) < n)++log;
        size = 1 << log;
        d.resize(2*size);

        for(int i=0; i<n; i++)d[i + size] = S(0, 1, i);
        for(int i=size - 1; i >= 1; i--)update(i);
    }

    S get(int p){
        assert(0 <= p && p < n);
        return d[p + size];
    }

    void set(int p, S v){
        assert(0 <= p && p < n);
        p += size;
        
        d[p] = v;
        for(int i=1; i<=log; i++)update(p>>i);
    }

    S get(int l, int r){
        assert(0 <= l && l <= r && r <= n);
        if(l == r)return S();
        l += size;
        r += size;

        S sml = S(), smr = S();
        while(l < r){
            if(l&1) sml = sml + d[l++];
            if(r&1) smr = d[--r] + smr;

            l >>= 1;
            r >>= 1;
        }

        return sml + smr;
    }

private :

    int n, log, size;
    vector<S> d;
    void update(int p){ d[p] = d[2*p] + d[2*p + 1]; }
};


struct node {
    int sm, sz, fi;
    explicit node(int s = 0,int l = 0,int f = INF) : sm(s), sz(l), fi(f) {};
    node operator +(const node &other){
        node res;
        res.sm = sm + other.sm;
        res.sz = sz + other.sz;
        res.fi = min(fi, other.fi);

        return res;
    }
};


int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, root;
    cin >> n >> m;
    vector<int> p(n);
    for(int i=0; i<n; i++){
        cin >> p[i];
        --p[i];
        if(p[i] != -1){
            adj[i].push_back(p[i]);
            adj[p[i]].push_back(i);
        }else root = i;
    }
    
    {   
        int c = 0;
        for(int i=0; i<n; i++){
            int curr = 0;
            while(curr != -1){
                if(pref[curr] < c)break;
                pref[curr] = c;
                curr = p[curr];
            }
            ++c;
        }
    }
    
    vector<int> id(n);
    dist[root] = 0;
    dfs(root, -1);
    for(int i=0; i<n; i++)id[order[i]] = i;

    set<int> tofill;
    for(int i=0; i<n; i++)tofill.insert(i);

    segment<node> K(n);
    for(int i=0; i<m; i++){
        int t, x;
        cin >> t >> x;
        if(t & 1){
            assert(x <= tofill.size());
            vector<int> tem;
            auto it = tofill.begin();
            for(int i=0; i<x; i++){
                K.set(*it, node(1, 1, INF));
                tem.push_back(*it);
                ++it;
            }
            cout << order[tem.back()] + 1 << '\n';
            for(int &c : tem)tofill.erase(c);
        }else {
            --x;
            int k = id[x];
            int cc = K.get(k, n).fi;
            cc = min(cc, n);
            --cc;
            K.set(cc, node(0, 1, cc));
            tofill.erase(cc);
            cout << dist[order[k]] - dist[order[cc]] << '\n';
        }
    }

    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from ballmachine.cpp:1:
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:132:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             assert(x <= tofill.size());
      |                    ~~^~~~~~~~~~~~~~~~
ballmachine.cpp:121:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |     dfs(root, -1);
      |     ~~~^~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 30
• Subtask 3: 8.571428571428571 / 40
• Subtask 4: 0 / 5