Submission #1124059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124059		CDuong	Ball Machine (BOI13_ballmachine)	C++20	8.57 / 100	1097 ms	25296 KiB

ballmachine

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

void solve() {
    int n, q;
    cin >> n >> q;

    vector<vector<int>> g(n);
    int root = -1;
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        if (val) {
            g[--val].emplace_back(i);
        }
        else {
            root = i;
        }
    }

    vector<int> mn(n), dep(n);
    iota(all(mn), 0);
    vector<vector<int>> par(n, vector<int>(20));
    auto dfs_p = [&](auto self, int u) -> void {
        for (int i = 1; i < 20; ++i) {
            par[u][i] = par[par[u][i - 1]][i - 1];
        }
        for (auto v : g[u]) {
            par[v][0] = u;
            dep[v] = dep[u] + 1;
            self(self, v);
            mn[v] = min(mn[v], mn[u]);
        }
    };
    par[root][0] = root;
    dfs_p(dfs_p, root);

    for (int i = 0; i < n; ++i) {
        sort(all(g[i]), [&](int x, int y) {
            return mn[x] < mn[y];
        });
    }

    int cres = -1;
    vector<int> a(n);
    auto dfs = [&](auto self, int u, int &val) -> void {
        for (auto v : g[u]) if (not a[v]) {
            self(self, v, val);
            if (val == 0) return;
        }
        a[u] = 1;
        if (--val == 0) {
            cres = u;
        }
    };

    while (q--) {
        int tp;
        cin >> tp;
        if (tp == 1) {
            int val;
            cin >> val;
            cres = -1;
            dfs(dfs, root, val);
            cout << cres + 1 << '\n';
        }
        else {
            int u;
            cin >> u;
            --u;
            int od = dep[u];
            for (int i = 19; i >= 0; --i) {
                if (a[par[u][i]]) u = par[u][i];
            }
            a[u] = 0;
            cout << od - dep[u] << "\n";
        }
    }
}

signed main() {

#ifndef CDuongg
    if (fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

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