Submission #493483

#	Time	Username	Problem	Language	Result	Execution time	Memory
493483		SangTin	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	175 ms	29252 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

#define name "BALLMACHINE"
#define endl '\n'
#define ednl endl
#define long long long
#define memset(a, x) memset(a, (x), sizeof(a));
#define inoutf freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define IN(a, b, c) (a <= b && b <= c)

template<typename T, typename U> inline bool amin(T &x, U y) { if(y >= x) return 0; x = y; return 1;}
template<typename T, typename U> inline bool amax(T &x, U y) { if(x >= y) return 0; x = y; return 1;}
template<typename T> inline void read(T& x){
    bool Neg = false;
    char c;
    for (c = getchar(); c < '0' | c > '9'; c = getchar())
        if (c == '-') Neg = !Neg;
    x = c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    if (Neg) x = -x;
}

const int N = 1e5 + 83;
vector <int> Graph[N];
int Min[N], Priority[N], cnt = 0, pa[N][30], h[N], rePriority[N];
bool Have[N];

bool comp(int a, int b){
    return Min[a] < Min[b];
}

int dfs(bool sta, int u, int pa){
    if (sta && pa != -1) h[u] = h[pa] + 1;
    Min[u] = u;
    for (int &v : Graph[u]){
        amin(Min[u], dfs(sta, v, u));
    }
    if (sta){
        Priority[++cnt] = u;
        rePriority[u] = cnt;
    }
    return Min[u];
}

struct segtree{
    int Size;
    vector <int> ord;

    void init(int n){
        Size = n;
        ord.assign(4 * n, 0);
    }

    void update(int &i, int &p, int x, int lx, int rx){
        if (lx == rx){
            ord[x] = p;
            return;
        }
        int mid = (lx + rx) >> 1;
        if (mid < i) update(i, p, x << 1 | 1, mid + 1, rx);
        else update(i, p, x << 1, lx, mid);
        ord[x] = ord[x << 1] + ord[x << 1 | 1];
    }
    void update(int i, int p){update(i, p, 1, 1, Size);}

    int get_prio(int k, int x, int lx, int rx){
        if (lx == rx) return Priority[lx];
        int mid = (lx + rx) >> 1;
        if (ord[x << 1] < k) return get_prio(k - ord[x << 1], x << 1 | 1, mid + 1, rx);
        return get_prio(k, x << 1, lx, mid);
    }
    int get_prio(int k){return get_prio(k, 1, 1, Size);}
}st;

int LCA(int u){
    int log = log2(h[u]);
    for (int i = log; i >= 0; --i){
        if (pa[u][i] != -1 && Have[pa[u][i]]) u = pa[u][i];
    }
    return u;
}

int Solve(){
    int n, q; cin >> n >> q;
    memset(pa, -1);
    for (int i = 1; i <= n; ++i){
        cin >> pa[i][0];
        Graph[pa[i][0]].push_back(i);
    }
    dfs(0, 0, -1);
    for (int i = 1; i <= n; ++i){
        sort(Graph[i].begin(), Graph[i].end(), comp);
    }
    h[0] = 0;
    dfs(1, 0, -1);

    memset(Have, 0);
    st.init(n);
    for (int i = 1; i <= n; ++i) st.update(i, 1);

    int log = log2(n);
    for (int j = 1; j <= log; ++j){
        for (int i = 1; i <= n; ++i){
            if (pa[i][j - 1] == -1) continue;
            pa[i][j] = pa[pa[i][j - 1]][j - 1];
        }
    }

    while (q--){
        int sta, x; cin >> sta >> x;
        switch (sta){
            case 1:{
                int last;
                while(x--){
                    last = st.get_prio(1);
                    Have[last] = 1;
                    st.update(rePriority[last], 0);
                }
                cout << last << endl;
                break;
            }
            case 2:{
                int farPa = LCA(x);
                cout << h[x] - h[farPa] << endl;
                st.update(rePriority[farPa], 1);
                Have[farPa] = 0;
                break;
            }
        }
    }

    return 0;
}

int main(){
    fastio;

    int t = 1;
//    cin >> t;
    while (t--){
        Solve();
    }

    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int Solve()':
ballmachine.cpp:6:14: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
    6 | #define endl '\n'
      |              ^~~~
ballmachine.cpp:117:21: note: 'last' was declared here
  117 |                 int last;
      |                     ^~~~

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