oj.uz

답안 #879989

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
879989 2023-11-28T14:11:06 Z Karoot Ball Machine (BOI13_ballmachine) C++17
100 / 100
 201 ms 56664 KB 
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
 
#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()
 
using namespace std;
 
typedef long long ll;
 
ll linf = 1e15+1;
 
inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}
 
const int MAXN = 2e5+1;
int parent[MAXN];
int binPar[MAXN][20];
vector<int> children[MAXN];
int childs[MAXN];
int vals[MAXN];
int minInSubtree[MAXN];
int root;
int indexToVal[MAXN];
int valToIndex[MAXN];
int hasBall[MAXN];
int indexToNode[MAXN];
int nodeToIndex[8*MAXN];
 
int initMinInSubtree(int node = root){
    int mini = node;
    for (auto& e : children[node]){
        mini = min(mini, initMinInSubtree(e));
    }
    return minInSubtree[node] = mini;
}
 
int x = 0;
int n, q; 
 
void initVals(int node = root){
    set<pair<int, int>> s;
    for (auto& e : children[node]){
        s.insert({minInSubtree[e], e});
    }
    
    for (auto& p : s){
        initVals(p.second);
    }
    indexToVal[x] = node;
    valToIndex[node] = x;
    vals[x++] = node;
    return;
}
 
void initBinPar(){
    for (int i = 1; i <= n; i++){
        binPar[i][0] = parent[i];
    }
 
    for (int j = 1; j < 20; j++){
        for (int i = 1; i <= n; i++){
            binPar[i][j] = binPar[binPar[i][j-1]][j-1];
        }
    }
    return;
}
 
pair<int, int> lastBallParent(int node){
    if (!hasBall[parent[node]])return {node, 0};
 
    int rolledBalls = 0;
    
    for (int i = 19; i >= 0; i--){
        if (hasBall[binPar[node][i]]){
            node = binPar[node][i];
            rolledBalls += (1 << i);
        }
    }
    return {node, rolledBalls};
}
 
int ST[8*MAXN];
int leftOf[8*MAXN], rightOf[8*MAXN];
 
void buildTree(int l, int r, int node = 1){
    leftOf[node] = l;
    rightOf[node] = r;
    if (l == r){
        ST[node] = 0;
        indexToNode[l] = node;
        nodeToIndex[node] = l;
        return;
    }
    int mid = (l+r)/2;
    buildTree(l, mid, 2*node);
    buildTree(mid+1, r, 2*node+1);
    ST[node] = 0;
}
 
void update1(int node){
    if (node == 0)return;
    ST[node] = min(ST[2*node], ST[2*node+1]);
    return update1(node/2);
}
 
void update(int node, int w){
    node = indexToNode[node];
    ST[node] = w;
    update1(node/2);
}
 
int closestEmpty(int node = 1){
    if (leftOf[node] == rightOf[node]){
        return nodeToIndex[node];
    }
    int a = 2*node, b = 2*node+1;
    if (ST[a] == 0)return closestEmpty(a);
    return closestEmpty(b);
}
 
int main(){
    scoobydoobydoo();
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> parent[i];
        children[parent[i]].push_back(i);
        childs[parent[i]]++;
        if (parent[i] == 0){
            root = i;
            //parent[i] = i;
        }
    }
    initMinInSubtree();
    initVals();
    initBinPar();
    buildTree(0, n-1);
 
    vector<ll> ans;
 
    while (q--){
        int t; cin >> t;
        if (t == 1){
            int k; cin >> k;
            int latest = -1;
            for (int i = 0; i < k; i++){
                int ind = closestEmpty();
                latest = ind;
                hasBall[indexToVal[ind]] = 1;
                update(ind, 1);
            }
            ans.push_back(indexToVal[latest]);
        } else {
            int x; cin >> x;
            pair<int, int> ballParent = lastBallParent(x);
            int indToRemove = valToIndex[ballParent.first];
            //cout << "SAVEME " << ballParent.first << " " << ballParent.second << endl;
            update(indToRemove, 0);
            hasBall[ballParent.first] = 0;
            ans.push_back(ballParent.second);
        }
    }
 
    for (auto& e : ans){
        cout << e << endl;
    }
 
 
    
 
 
 
 
    return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 20828 KB Output is correct
2 Correct 158 ms 32472 KB Output is correct
3 Correct 142 ms 32616 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 20828 KB Output is correct
6 Correct 4 ms 20824 KB Output is correct
7 Correct 6 ms 20828 KB Output is correct
8 Correct 5 ms 21004 KB Output is correct
9 Correct 14 ms 21084 KB Output is correct
10 Correct 33 ms 23980 KB Output is correct
11 Correct 158 ms 32460 KB Output is correct
12 Correct 139 ms 32456 KB Output is correct
13 Correct 158 ms 32464 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 30992 KB Output is correct
2 Correct 178 ms 46608 KB Output is correct
3 Correct 152 ms 36132 KB Output is correct
4 Correct 119 ms 32792 KB Output is correct
5 Correct 125 ms 33100 KB Output is correct
6 Correct 118 ms 32884 KB Output is correct
7 Correct 117 ms 31064 KB Output is correct
8 Correct 110 ms 31068 KB Output is correct
9 Correct 175 ms 45536 KB Output is correct
10 Correct 176 ms 46672 KB Output is correct
11 Correct 170 ms 46636 KB Output is correct
12 Correct 171 ms 41252 KB Output is correct
13 Correct 159 ms 53584 KB Output is correct
14 Correct 151 ms 36048 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 34388 KB Output is correct
2 Correct 182 ms 41552 KB Output is correct
3 Correct 128 ms 51280 KB Output is correct
4 Correct 119 ms 42576 KB Output is correct
5 Correct 122 ms 43340 KB Output is correct
6 Correct 117 ms 43348 KB Output is correct
7 Correct 115 ms 38696 KB Output is correct
8 Correct 126 ms 51288 KB Output is correct
9 Correct 186 ms 45648 KB Output is correct
10 Correct 187 ms 46740 KB Output is correct
11 Correct 184 ms 46672 KB Output is correct
12 Correct 191 ms 41752 KB Output is correct
13 Correct 201 ms 56664 KB Output is correct
14 Correct 168 ms 36632 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 198 ms 45796 KB Output is correct
2 Correct 180 ms 41720 KB Output is correct
3 Correct 167 ms 56404 KB Output is correct
4 Correct 197 ms 45956 KB Output is correct
5 Correct 192 ms 46676 KB Output is correct
6 Correct 178 ms 46680 KB Output is correct
7 Correct 182 ms 41708 KB Output is correct
8 Correct 170 ms 56404 KB Output is correct
9 Correct 151 ms 36048 KB Output is correct