oj.uz

답안 #894683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
894683 2023-12-28T17:10:43 Z dwuy Ball Machine (BOI13_ballmachine) C++14
41.9231 / 100
 128 ms 23724 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);
    priority_queue<pair<int, int>> Q;
    for(int i=1; i<=n; i++) if(G[i].size() == 0){
        Q.push({-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 u = Q.top().se; Q.pop();
                ans = u;
                smt.update(num[u], clo[u], 1);
                if(++cnt[p[u][0]] == (int)G[p[u][0]].size()){
                    Q.push({-num[p[u][0]], p[u][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);
            cout << h << endl;
        }
    }
}

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

    nhap();
    solve();

    return 0;
}

Subtask #1
1.92307692308 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 6748 KB Output isn't correct
2 Incorrect 66 ms 14800 KB Output isn't correct
3 Incorrect 48 ms 14816 KB Output isn't correct
4 Incorrect 2 ms 6748 KB Output isn't correct
5 Incorrect 1 ms 6748 KB Output isn't correct
6 Correct 2 ms 6748 KB Output is correct
7 Incorrect 2 ms 6748 KB Output isn't correct
8 Incorrect 2 ms 6748 KB Output isn't correct
9 Incorrect 5 ms 6884 KB Output isn't correct
10 Incorrect 14 ms 9564 KB Output isn't correct
11 Incorrect 66 ms 14792 KB Output isn't correct
12 Incorrect 46 ms 14800 KB Output isn't correct
13 Incorrect 61 ms 14656 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 11624 KB Output isn't correct
2 Incorrect 98 ms 19748 KB Output isn't correct
3 Incorrect 57 ms 16068 KB Output isn't correct
4 Incorrect 42 ms 12112 KB Output isn't correct
5 Incorrect 46 ms 12360 KB Output isn't correct
6 Incorrect 48 ms 12120 KB Output isn't correct
7 Incorrect 45 ms 11344 KB Output isn't correct
8 Incorrect 23 ms 11612 KB Output isn't correct
9 Incorrect 87 ms 20016 KB Output isn't correct
10 Incorrect 99 ms 19744 KB Output isn't correct
11 Incorrect 102 ms 19920 KB Output isn't correct
12 Incorrect 98 ms 17888 KB Output isn't correct
13 Incorrect 56 ms 21988 KB Output isn't correct
14 Incorrect 55 ms 15936 KB Output isn't correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 15620 KB Output is correct
2 Correct 103 ms 18072 KB Output is correct
3 Correct 73 ms 21088 KB Output is correct
4 Correct 60 ms 17964 KB Output is correct
5 Correct 65 ms 17616 KB Output is correct
6 Correct 64 ms 17864 KB Output is correct
7 Correct 61 ms 16340 KB Output is correct
8 Correct 59 ms 20868 KB Output is correct
9 Correct 94 ms 19992 KB Output is correct
10 Correct 99 ms 19664 KB Output is correct
11 Correct 109 ms 19664 KB Output is correct
12 Correct 107 ms 18220 KB Output is correct
13 Correct 93 ms 23724 KB Output is correct
14 Correct 84 ms 16252 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 96 ms 20128 KB Output isn't correct
2 Incorrect 99 ms 18128 KB Output isn't correct
3 Incorrect 59 ms 23376 KB Output isn't correct
4 Incorrect 111 ms 20180 KB Output isn't correct
5 Incorrect 128 ms 19924 KB Output isn't correct
6 Incorrect 102 ms 19688 KB Output isn't correct
7 Incorrect 102 ms 18168 KB Output isn't correct
8 Incorrect 59 ms 23380 KB Output isn't correct
9 Incorrect 57 ms 16072 KB Output isn't correct