Submission #336051

#TimeUsernameProblemLanguageResultExecution timeMemory
336051sangpham2710Ball Machine (BOI13_ballmachine)C++14
100 / 100
259 ms29408 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define int long long #define fi first #define se second #define pb push_back #define pf push_front #define mp make_pair #define ms(a, b) memset((a), (b), sizeof(a)) #define len(a) (int)((a).size()) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define lb lower_bound #define ub upper_bound #define mine min_element #define maxe max_element #define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i) #define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define ford(i, a, b) for (int i = (a), _b = (b); i >= _b; --i) void __print(signed x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char* x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename F, typename S> void __print(const pair<F, S> &x) {cerr << '{'; __print(x.fi); cerr << ','; __print(x.se); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto& i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename F, typename... S> void _print(F t, S... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef SHANK #define bug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define bug(x...) #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template <class T> bool mini(T& a, const T& b) { return a > b ? (a = b, 1) : 0; } template <class T> bool maxi(T& a, const T& b) { return a < b ? (a = b, 1) : 0; } template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; using i64 = long long; using ld = long double; using pi = pair<int, int>; using ti = pair<int, pi>; using vi = vector<int>; using vpi = vector<pi>; using vti = vector<ti>; using vvi = vector<vi>; using vvpi = vector<vpi>; using vvti = vector<vti>; const int inf = (int)0x3f3f3f3f3f3f3f3f; const int ninf = (int)0xc0c0c0c0c0c0c0c0; const int mod = (int)1e9 + 7; const ld eps = (ld)1e-9; const int N = 1e5 + 3; const int LG = __lg(N) + 3; int n, q, root, p[N][LG], mn[N], h[N], ord[N], cnt; bool b[N]; vi a[N]; struct cmp { bool operator ()(const int &u, const int &v) { return ord[u] > ord[v]; } }; priority_queue<int, vi, cmp> vtx; void input() { cin >> n >> q; fort(u, 1, n) { cin >> p[u][0]; if (p[u][0] == 0) root = u; a[p[u][0]].pb(u); } } void dfsMin(int u) { mn[u] = u; for (int &v : a[u]) { h[v] = h[u] + 1; dfsMin(v); mini(mn[u], mn[v]); } } void dfsOrd(int u) { for (int &v : a[u]) dfsOrd(v); ord[u] = ++cnt; } void prep() { fort(i, 1, LG) fort(u, 1, n) if (p[u][i - 1]) { p[u][i] = p[p[u][i - 1]][i - 1]; } dfsMin(root); fort(i, 1, n) sort(all(a[i]), [&](const int &u, const int &v) { return mn[u] < mn[v]; }); dfsOrd(root); fort(i, 1, n) vtx.push(i); } int add() { int u = vtx.top(); vtx.pop(); b[u] = 1; return u; } int rmv(int u) { int res = h[u]; ford(i, LG - 1, 0) if (b[p[u][i]]) u = p[u][i]; b[u] = 0; vtx.push(u); return res - h[u]; } void solve() { prep(); fort(i, 1, q) { int t; cin >> t; if (t == 1) { int k; cin >> k; int ans; fort(i, 1, k) ans = add(); cout << ans << '\n'; } else { int u; cin >> u; cout << rmv(u) << '\n'; } } } signed main() { #ifdef SHANK freopen("CP.inp", "r", stdin); // freopen("CP.out", "w", stdout); #else // freopen("CP.inp", "r", stdin); // freopen("CP.out", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); input(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...