Submission #648189

#	Time	Username	Problem	Language	Result	Execution time	Memory
648189		LeonaRaging	Ball Machine (BOI13_ballmachine)	C++14	16.23 / 100	1084 ms	34128 KiB

ballmachine

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

#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const ll mod = 1e9 + 7;
const int maxn = 1e5 + 4;
const int INF = 1e9;
const int N = 20;

int n, q, root, f[maxn], h[maxn], up[maxn][20], tin[maxn];
bool has[maxn];
vector<int> adj[maxn];
set<pair<int,int>> mySet;

void dfs(int u) {
    for (int j = 1; j <= N; j++)
        up[u][j] = up[up[u][j - 1]][j - 1];
    f[u] = u;
    for (int v : adj[u]) {
        h[v] = h[u] + 1;
        up[v][0] = u;
        dfs(v);
        f[u] = min(f[u], f[v]);
    }
}

void dfs2(int u) {
    vector<pair<int,int>> ord;
    for (int v : adj[u])
        ord.pb({f[v], v});
    sort(ord.begin(), ord.end());
    for (auto it : ord)
        dfs2(it.se);
    tin[u] = ++tin[0];
    mySet.insert({tin[u], u});
}

int jump(int u) {
    for (int j = N; j >= 0; j--)
        if (has[up[u][j]])
            u = up[u][j];
    return u;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int p; cin >> p;
        if (p) adj[p].pb(i);
        else root = i;
    }
    dfs(root);
    dfs2(root);
    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int k; cin >> k;
            while (k--) {
                auto it = *mySet.begin();
                has[it.se] = 1;
                mySet.erase(mySet.begin());
                if (k == 0) cout << it.se << '\n';
            }
        }
        else {
            int u; cin >> u;
            int p = jump(u);
            has[p] = 0;
            mySet.insert({tin[p], p});
            cout << h[u] - h[p] << '\n';
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs(int)':
ballmachine.cpp:22:18: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
   22 |         up[u][j] = up[up[u][j - 1]][j - 1];
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:21:23: note: within this loop
   21 |     for (int j = 1; j <= N; j++)
      |                     ~~^~~~

• Subtask 1: 3.8461538461538463 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 0 / 40
• Subtask 4: 1.6666666666666667 / 5