oj.uz

Submission #617957

# Submission time Handle Problem Language Result Execution time Memory
617957 2022-08-01T17:58:13 Z qualdum Ball Machine (BOI13_ballmachine) C++17
100 / 100
 444 ms 42324 KB 
#include "bits/stdc++.h"

using namespace std;

#define int long long
#define sz(v) ((int)(v).size())
#define all(a) (a).begin(),  (a).end()
#define rall(a) a.rbegin(), a.rend()
#define F first
#define S second
#define time (double)clock() / (double)CLOCKS_PER_SEC

using pii = pair<int, int>;
using ll = long long;
using ld = long double;

const ll infll = (ll)4e18 + 27;
const ll inf = (ll)1e9 + 27;
const ll mod = (ll)1e9 + 7;

#ifdef home
#define dbg(x) cout << #x << " = " << (x) << endl
#else
#define dbg(x) 228
#endif

template <class T>
using pq = priority_queue <T, vector <T>, less <T>>;
template <class T>
using pqr = priority_queue <T, vector <T>, greater <T>>;

template <typename T, typename T2>
istream& operator>> (istream& in, pair<T, T2>& b) {
    in >> b.first >> b.second;
    return in;
}

template <typename T, typename T2>
ostream& operator<< (ostream& out, const pair<T, T2>& b) {
    out << "{" << b.first << ", " << b.second << "}";
    return out;
}

template <typename T>
istream& operator>> (istream& in, vector<T>& b) {
    for(auto &v: b) {
        in >> v;
    }
    return in;
}

template <typename T>
ostream& operator<< (ostream& out, vector<T>& b) {
    for(auto &v: b) {
        out << v << ' ';
    }
    return out;
}

template <typename T>
ostream& operator<< (ostream& out, deque<T>& b) {
    for(auto &v: b) {
        out << v << ' ';
    }
    return out;
}

template <typename T>
void print(T x, string end = "\n") {
    cout << x << end;
}

template <typename T1, typename T2> bool chkmin(T1 &x, const T2 &y) { return x > y && (x = y, true); }
template <typename T1, typename T2> bool chkmax(T1 &x, const T2 &y) { return x < y && (x = y, true); }

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 1e5 + 10, LOG = 20;
int up[N][LOG];
vector<int> g[N];
set<pii> st;
int timer[N], cur = 1;
bool ok[N];
int h[N];

int calc(int u){
    int mn = inf;
    vector<pii> nw;
    for(int i = 0;i < sz(g[u]);i++){
        int x = calc(g[u][i]);
        nw.push_back({x, g[u][i]});
        mn = min(mn, x);
    }
    sort(all(nw));
    g[u].clear();
    for(auto [x, y]: nw){
        g[u].push_back(y);
    }
    mn = min(mn, u);
    return mn;
}

void dfs(int u, int p = -1){
    h[u] = (p == -1 ? 0 : h[p] + 1);
    for(int i = 0;i < LOG - 1;i++){
        up[u][i + 1] = up[up[u][i]][i];
    }
    for(auto v: g[u]){
        up[v][0] = u;
        dfs(v, u);
    }
    timer[u] = cur++;
    st.insert({timer[u], u});
}

int add(int k){
    int last = -1;
    for(int i = 0;i < k;i++){
        auto [x, y] = *st.begin();
        st.erase(st.begin());
        last = y;
        ok[y] = true;
    }
    return last;
}

int remove(int k){
    int doll = 0;
    int u = k;
    int t = up[u][LOG - 1];
    if(ok[t]){
        ok[t] = false;
        st.insert({timer[t], t});
        return h[k];
    }
    for(int i = LOG - 1;i >= 0;i--){
        if(ok[up[u][i]]){
            u = up[u][i];
            doll += (1ll << i);
        }
    }
    if(u == k){
        ok[u] = false;
        st.insert({timer[u], u});
        return 0;
    }
    ok[u] = false;
    st.insert({timer[u], u});
    return doll;
}

void solve() {
    int n, q;
    cin >> n >> q;
    int root = 0;
    for(int i = 1;i <= n;i++){
        int x;
        cin >> x;
        if(x == 0){
            root = i;
        } else {
            g[x].push_back(i);
        }
    }
    calc(root);
    up[root][0] = root;
    dfs(root);
    while (q--){
        int t, k;
        cin >> t >> k;
        if(t == 1){
            cout << add(k) << endl;
        } else {
            cout << remove(k) << endl;
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cout << fixed << setprecision(15);
    int32_t t = 1;
    //cin >> t;
#ifndef home
    //freopen("fcount.in", "r", stdin);
    //freopen("fcount.out", "w", stdout);
#endif
    while(t--)
        solve();
#ifdef home
    cout << "_________________________________" << endl;
    cout << "finished in " << time << " s";
#endif
    return 0;
}

/*
8 18
2
0
1
1
3
3
4
6
1 8
2 8
2 8
2 8
2 8
2 8
2 7
2 7
2 5
1 8
2 8
2 8
2 8
2 8
2 8
2 7
2 7
2 5
 */

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 270 ms 19308 KB Output is correct
3 Correct 193 ms 19444 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 4 ms 2944 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 4 ms 2900 KB Output is correct
9 Correct 17 ms 3668 KB Output is correct
10 Correct 47 ms 6852 KB Output is correct
11 Correct 240 ms 19348 KB Output is correct
12 Correct 202 ms 19496 KB Output is correct
13 Correct 222 ms 19340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 10044 KB Output is correct
2 Correct 309 ms 34868 KB Output is correct
3 Correct 213 ms 27868 KB Output is correct
4 Correct 151 ms 12540 KB Output is correct
5 Correct 182 ms 12748 KB Output is correct
6 Correct 155 ms 12264 KB Output is correct
7 Correct 165 ms 10784 KB Output is correct
8 Correct 156 ms 10060 KB Output is correct
9 Correct 290 ms 35108 KB Output is correct
10 Correct 318 ms 34652 KB Output is correct
11 Correct 280 ms 34876 KB Output is correct
12 Correct 309 ms 30916 KB Output is correct
13 Correct 239 ms 37492 KB Output is correct
14 Correct 225 ms 27776 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 18916 KB Output is correct
2 Correct 320 ms 31792 KB Output is correct
3 Correct 231 ms 34348 KB Output is correct
4 Correct 225 ms 28844 KB Output is correct
5 Correct 221 ms 28376 KB Output is correct
6 Correct 208 ms 28324 KB Output is correct
7 Correct 223 ms 25880 KB Output is correct
8 Correct 241 ms 34288 KB Output is correct
9 Correct 340 ms 35340 KB Output is correct
10 Correct 346 ms 34908 KB Output is correct
11 Correct 418 ms 34860 KB Output is correct
12 Correct 386 ms 31792 KB Output is correct
13 Correct 444 ms 42324 KB Output is correct
14 Correct 315 ms 28256 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 35352 KB Output is correct
2 Correct 400 ms 31856 KB Output is correct
3 Correct 310 ms 42188 KB Output is correct
4 Correct 372 ms 35368 KB Output is correct
5 Correct 311 ms 34944 KB Output is correct
6 Correct 315 ms 34800 KB Output is correct
7 Correct 353 ms 31812 KB Output is correct
8 Correct 260 ms 42132 KB Output is correct
9 Correct 213 ms 27864 KB Output is correct