oj.uz

Submission #894688

# Submission time Handle Problem Language Result Execution time Memory
894688 2023-12-28T17:32:15 Z dwuy Ball Machine (BOI13_ballmachine) C++14
100 / 100
 182 ms 23544 KB 
/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;

struct SMT{
    int n;
    vector<int> tree;

    SMT(int n=0){
        this->n = n;
        this->tree.assign(n<<2|1, 0);
    }

    void down(int id){
        if(tree[id]==0) return;
        tree[id<<1] += tree[id];
        tree[id<<1|1] += tree[id];
        tree[id] = 0;
    }

    void update(int l, int r, int id, const int &u, const int &v, const int &val){
        if(l>v || r<u) return;
        if(l>=u && r<=v){
            tree[id] += val;
            return;
        }
        down(id);
        int mid = (l+r)>>1;
        update(l, mid, id<<1, u, v, val);
        update(mid+1, r, id<<1|1, u, v, val);
    }

    void update(int l, int r, int val){
        update(1, n, 1, l, r, val);
    }

    int get(int pos){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            down(id);
            int mid = (lo+hi)>>1;
            if(pos<=mid) id = id<<1, hi = mid;
            else lo = mid + 1, id = id<<1|1;
        }
        return tree[id];
    }
};

const int MX = 100005;
int n, q;
vector<int> G[MX];

void nhap(){
    cin >> n >> q;
    for(int i=1; i<=n; i++){
        int u; cin >> u;
        G[u].push_back(i);
    }
}

int p[MX][17];
int num[MX];
int clo[MX];
int mnID[MX];
int dfsID = 0;

void calcID(int u){
    mnID[u] = u;
    for(int v: G[u]){
        calcID(v);
        p[v][0] = u;
        mnID[u] = min(mnID[u], mnID[v]);
    }
}

bool comp(const int &a, const int &b){
    return mnID[a] < mnID[b];
}

void dfs(int u){
    num[u] = ++dfsID;
    sort(G[u].begin(), G[u].end(), comp);
    for(int v: G[u]) dfs(v);
    clo[u] = dfsID;
}

int cnt[MX];

void solve(){
    int root = G[0][0];
    calcID(root);
    dfs(root);
    set<pair<int, int>> Q;
    for(int i=1; i<=n; i++) if(G[i].size() == 0){
        Q.insert({num[i], i});
    }
    for(int j=1; j<=16; j++){
        for(int i=1; i<=n; i++){
            p[i][j] = p[p[i][j-1]][j-1];
        }
    }
    SMT smt(n);
    while(q--){
        int oper, u;
        cin >> oper >> u;
        if(oper == 1){
            int ans = 0;
            while(u--){
                int v = Q.begin()->se; Q.erase(Q.begin());
                ans = v;
                smt.update(num[v], clo[v], 1);
                if(++cnt[p[v][0]] == (int)G[p[v][0]].size()){
                    Q.insert({num[p[v][0]], p[v][0]});
                }
            }
            cout << ans << endl;
        }
        if(oper == 2){
            int h = smt.get(num[u]) - 1;
            int v = u;
            for(int t=h; t; t-=-t&t) v = p[v][__lg(-t&t)];
            smt.update(num[v], clo[v], -1);
            if(cnt[p[v][0]] == (int)G[p[v][0]].size()){
                Q.erase(Q.find({num[p[v][0]], p[v][0]}));
            }
            cnt[p[v][0]]--;
            Q.insert({num[v], v});
            cout << h << endl;
        }
    }
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 102 ms 15408 KB Output is correct
3 Correct 48 ms 15684 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 7 ms 7080 KB Output is correct
10 Correct 21 ms 10020 KB Output is correct
11 Correct 107 ms 15548 KB Output is correct
12 Correct 47 ms 15404 KB Output is correct
13 Correct 93 ms 15480 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 11352 KB Output is correct
2 Correct 138 ms 20564 KB Output is correct
3 Correct 58 ms 17592 KB Output is correct
4 Correct 91 ms 11948 KB Output is correct
5 Correct 74 ms 11988 KB Output is correct
6 Correct 62 ms 11860 KB Output is correct
7 Correct 63 ms 11388 KB Output is correct
8 Correct 27 ms 11612 KB Output is correct
9 Correct 102 ms 20304 KB Output is correct
10 Correct 136 ms 20564 KB Output is correct
11 Correct 112 ms 20756 KB Output is correct
12 Correct 113 ms 18772 KB Output is correct
13 Correct 57 ms 21680 KB Output is correct
14 Correct 69 ms 17628 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 15956 KB Output is correct
2 Correct 127 ms 19180 KB Output is correct
3 Correct 81 ms 20840 KB Output is correct
4 Correct 71 ms 18512 KB Output is correct
5 Correct 77 ms 18516 KB Output is correct
6 Correct 82 ms 18628 KB Output is correct
7 Correct 81 ms 17220 KB Output is correct
8 Correct 68 ms 20636 KB Output is correct
9 Correct 131 ms 20652 KB Output is correct
10 Correct 126 ms 20728 KB Output is correct
11 Correct 182 ms 20788 KB Output is correct
12 Correct 128 ms 19028 KB Output is correct
13 Correct 103 ms 23544 KB Output is correct
14 Correct 127 ms 17900 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 20700 KB Output is correct
2 Correct 121 ms 19028 KB Output is correct
3 Correct 60 ms 22864 KB Output is correct
4 Correct 118 ms 20568 KB Output is correct
5 Correct 122 ms 20820 KB Output is correct
6 Correct 105 ms 20560 KB Output is correct
7 Correct 125 ms 19280 KB Output is correct
8 Correct 60 ms 22868 KB Output is correct
9 Correct 60 ms 17456 KB Output is correct