oj.uz

Submission #336050

# Submission time Handle Problem Language Result Execution time Memory
336050 2020-12-14T14:57:04 Z sangpham2710 Ball Machine (BOI13_ballmachine) C++14
91.4286 / 100
 241 ms 29152 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 + 1;
const int LG = __lg(N) + 1;

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 2924 KB Output is correct
2 Correct 124 ms 16100 KB Output is correct
3 Correct 77 ms 15972 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 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 7 ms 3564 KB Output is correct
10 Correct 23 ms 6124 KB Output is correct
11 Correct 116 ms 16100 KB Output is correct
12 Correct 80 ms 15972 KB Output is correct
13 Correct 103 ms 16192 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 8040 KB Output is correct
2 Correct 183 ms 25572 KB Output is correct
3 Correct 95 ms 21984 KB Output is correct
4 Correct 67 ms 10216 KB Output is correct
5 Correct 69 ms 10088 KB Output is correct
6 Correct 63 ms 10088 KB Output is correct
7 Correct 69 ms 9288 KB Output is correct
8 Correct 39 ms 8044 KB Output is correct
9 Correct 164 ms 25956 KB Output is correct
10 Correct 193 ms 25316 KB Output is correct
11 Correct 149 ms 25316 KB Output is correct
12 Correct 167 ms 23704 KB Output is correct
13 Correct 124 ms 25828 KB Output is correct
14 Correct 90 ms 21984 KB Output is correct

Subtask #3
31.4285714286 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 14436 KB Output is correct
2 Correct 196 ms 24352 KB Output is correct
3 Incorrect 147 ms 23656 KB Output isn't correct
4 Correct 130 ms 21220 KB Output is correct
5 Correct 131 ms 20832 KB Output is correct
6 Correct 126 ms 20832 KB Output is correct
7 Correct 150 ms 19808 KB Output is correct
8 Incorrect 166 ms 23656 KB Output isn't correct
9 Correct 213 ms 25960 KB Output is correct
10 Correct 212 ms 25576 KB Output is correct
11 Correct 212 ms 25572 KB Output is correct
12 Correct 210 ms 24296 KB Output is correct
13 Incorrect 241 ms 29152 KB Output isn't correct
14 Correct 142 ms 22628 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 26084 KB Output is correct
2 Correct 193 ms 24296 KB Output is correct
3 Correct 144 ms 28640 KB Output is correct
4 Correct 205 ms 26212 KB Output is correct
5 Correct 196 ms 25572 KB Output is correct
6 Correct 170 ms 25644 KB Output is correct
7 Correct 196 ms 24296 KB Output is correct
8 Correct 136 ms 28640 KB Output is correct
9 Correct 94 ms 22116 KB Output is correct