Submission #666275

#	Time	Username	Problem	Language	Result	Execution time	Memory
666275		vuavisao	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	186 ms	24312 KiB

ballmachine

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;

template<typename Lhs, typename Rhs> inline void Max_self(Lhs &a, Rhs b) { a = (a > b ? a : b); }
template<typename Lhs, typename Rhs> inline void Min_self(Lhs &a, Rhs b) { a = (a < b ? a : b); }

const int N = 1e5 + 10;

void dfs_more_and_more(int u);
void dfs_calc(int u);
void pre_calc();
int first_parent(int u);

int n, q;
vector<int> g[N];

int root;
int Lg, dist[N], parent[20][N];

bool have[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int cnt, in[N];
int dp[N];

void dfs_more_and_more(int u) {
    dp[u] = u;
    for(auto v : g[u]) {
        dist[v] = dist[u] + 1;
        parent[0][v] = u;
        dfs_more_and_more(v);
        Min_self(dp[u], dp[v]);
    }
}

void dfs_calc(int u) {
    sort(g[u].begin(), g[u].end(), [&] (int lhs, int rhs) {
        if(dp[lhs] != dp[rhs]) return dp[lhs] < dp[rhs];
        return lhs < rhs;
    });
    for(auto v : g[u]) dfs_calc(v);
    in[u] = ++ cnt;
    pq.push(make_pair(in[u], u));
}

int first_parent(int u) {
    for(int i = Lg; i >= 0; -- i)
        if(have[parent[i][u]] & 1) u = parent[i][u];
    return u;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("Ball.inp", "r")) {
        freopen("Ball.inp", "r", stdin);
        freopen("Ball.out", "w", stdout);
    }
    cin >> n >> q;
    for(int v = 1; v <= n; ++ v) {
        int u; cin >> u;
        if(u == 0) root = v;
        else g[u].push_back(v);
//        cout << u << ' ' << v << '\n';
    }
    pre_calc();
    while(q--) {
        int type; cin >> type;
        if(type == 1) {
            int k; cin >> k;
            while(k--) {
                auto psy = pq.top(); pq.pop();
                have[psy.second] = true;
                if(k == 0) cout << psy.second;
            }
        }
        else {
            int u; cin >> u;
            int p = first_parent(u);
            have[p] = false;
            pq.push(make_pair(in[p], p));
//            cout << u << ' ' << p << ' ';
            cout << dist[u] - dist[p];
        }
        cout << '\n';
    }
    return 0;
}

void pre_calc() {
    dfs_more_and_more(root);
    dfs_calc(root);

    Lg = __lg(n);
    for(int j = 1; j <= Lg; ++ j)
        for(int i = 1; i <= n; ++ i)
            parent[j][i] = parent[j - 1][parent[j - 1][i]];
}

/// Code by vuavisao

Compilation message (stderr)

ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen("Ball.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen("Ball.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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