oj.uz

Submission #336051

# Submission time Handle Problem Language Result Execution time Memory
336051 2020-12-14T14:58:44 Z sangpham2710 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 259 ms 29408 KB 
#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;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 125 ms 15964 KB Output is correct
3 Correct 79 ms 16100 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2924 KB Output is correct
7 Correct 3 ms 2924 KB Output is correct
8 Correct 3 ms 2924 KB Output is correct
9 Correct 8 ms 3564 KB Output is correct
10 Correct 22 ms 6124 KB Output is correct
11 Correct 128 ms 16100 KB Output is correct
12 Correct 80 ms 16100 KB Output is correct
13 Correct 111 ms 15972 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 7916 KB Output is correct
2 Correct 184 ms 25572 KB Output is correct
3 Correct 107 ms 22756 KB Output is correct
4 Correct 69 ms 9832 KB Output is correct
5 Correct 72 ms 9704 KB Output is correct
6 Correct 66 ms 9704 KB Output is correct
7 Correct 69 ms 8936 KB Output is correct
8 Correct 38 ms 7912 KB Output is correct
9 Correct 180 ms 25960 KB Output is correct
10 Correct 191 ms 25572 KB Output is correct
11 Correct 153 ms 25700 KB Output is correct
12 Correct 179 ms 23908 KB Output is correct
13 Correct 123 ms 26080 KB Output is correct
14 Correct 96 ms 22628 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 14440 KB Output is correct
2 Correct 214 ms 24620 KB Output is correct
3 Correct 165 ms 23916 KB Output is correct
4 Correct 147 ms 21500 KB Output is correct
5 Correct 172 ms 21220 KB Output is correct
6 Correct 137 ms 21220 KB Output is correct
7 Correct 132 ms 20196 KB Output is correct
8 Correct 156 ms 23916 KB Output is correct
9 Correct 212 ms 26216 KB Output is correct
10 Correct 210 ms 25704 KB Output is correct
11 Correct 226 ms 25752 KB Output is correct
12 Correct 224 ms 24824 KB Output is correct
13 Correct 259 ms 29408 KB Output is correct
14 Correct 138 ms 22760 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 26344 KB Output is correct
2 Correct 199 ms 24552 KB Output is correct
3 Correct 140 ms 29152 KB Output is correct
4 Correct 228 ms 26212 KB Output is correct
5 Correct 211 ms 25796 KB Output is correct
6 Correct 172 ms 25704 KB Output is correct
7 Correct 211 ms 24552 KB Output is correct
8 Correct 151 ms 29024 KB Output is correct
9 Correct 99 ms 22696 KB Output is correct