oj.uz

답안 #950441

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950441 2024-03-20T10:13:24 Z phoenix0423 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 764 ms 37224 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long 
const int maxn = 1e5 + 5;
int dep[maxn], succ[maxn][18], in[maxn], out[maxn], dfn = 0;
vector<int> adj[maxn];
int st[maxn * 4], tag[maxn * 4], id[maxn];
int mn[maxn];
int n, q;

void dfs1(int pos){
    mn[pos] = pos;
    for(auto x : adj[pos]){
        dfs1(x);
        mn[pos] = min(mn[pos], mn[x]);
    }
}
void dfs(int pos, int prev){
    sort(adj[pos].begin(), adj[pos].end(), [&](int a, int b){ return mn[a] < mn[b];});
    in[pos] = dfn;
    succ[pos][0] = prev;
    for(int i = 1; i < 18; i++) succ[pos][i] = succ[succ[pos][i - 1]][i - 1];
    for(auto x : adj[pos]){
        dep[x] = dep[pos] + 1;
        dfs(x, pos);
    }
    out[pos] = dfn++;
    id[out[pos]] = pos;
}

void push(int v, int l, int r){
    int m = (l + r) / 2;
    if(tag[v]){
        st[v * 2] = (m - l + 1), tag[v * 2] = 1;
        st[v * 2 + 1] = (r - m), tag[v * 2 + 1] = 1;
        tag[v] = 0;
    }
}

int add(int val, int v = 1, int l = 0, int r = n - 1){
    // cout<<"add : "<<val<<" "<<l<<" "<<r<<"\n";
    st[v] += val;
    if(l == r) return l;
    int m = (l + r) / 2;
    push(v, l, r);
    if(m - l + 1 - st[v * 2] >= val){
        return add(val, v * 2, l, m);
    }
    else{
        int lft = val - (m - l + 1 - st[v * 2]);
        st[v * 2] = m - l + 1, tag[v * 2] = 1;
        return add(lft, v * 2 + 1, m + 1, r);
    }
}

int qry(int pos, int v = 1, int l = 0, int r = n - 1){
    if(l == r) return st[v];
    int m = (l + r) / 2;
    push(v, l, r);
    if(pos <= m) return qry(pos, v * 2, l, m);
    else return qry(pos, v * 2 + 1, m + 1, r);
}

void upd(int pos, int val, int v = 1, int l = 0, int r = n - 1){
    if(l == r){
        // cout<<"upd : "<<pos<<" "<<val<<"\n";
        st[v] += val;
        return;
    }
    push(v, l, r);
    int m = (l + r) / 2;
    if(pos <= m) upd(pos, val, v * 2, l, m);
    else upd(pos, val, v * 2 + 1, m + 1, r);
    st[v] = st[v * 2] + st[v * 2 + 1];
}

int lift(int pos, int steps){
    for(int i = 17; i >= 0; i--){
        if(steps & (1 << i)) pos = succ[pos][i];
    }
    return pos;
}
signed main(void){
    // fastio;
    cin>>n>>q;
    int rt = 0;
    for(int i = 0; i < n; i++){
        int x;
        cin>>x;
        if(x == 0) rt = i;
        else x--, adj[x].pb(i);
    }
    dfs1(rt);
    dfs(rt, rt);
    // cout<<"out : ";
    // for(int i = 0; i < n; i++) cout<<out[i]<<" ";
    // cout<<"\n";
    int ttl = 0;
    for(int i = 0; i < q; i++){
        int op, k;
        cin>>op>>k;
        // cout<<"ttl : "<<qry(out[0])<<"\n";
        if(op == 1){
            cout<<id[add(k)] + 1<<"\n";
        }
        else{
            k--;
            int l = 0, r = dep[k] + 1;
            while(l + 1 < r){
                int m = (l + r) / 2;
                int id = lift(k, m);
                // cout<<"ck : "<<id<<" "<<qry(out[id])<<"\n";
                if(qry(out[id])) l = m;
                else r = m;
            }
            cout<<l<<"\n";
            int x = lift(k, l);
            upd(out[x], -1);
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:105:9: warning: unused variable 'ttl' [-Wunused-variable]
  105 |     int ttl = 0;
      |         ^~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 265 ms 24936 KB Output is correct
3 Correct 193 ms 21908 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 3 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 23 ms 9052 KB Output is correct
10 Correct 47 ms 11688 KB Output is correct
11 Correct 252 ms 24792 KB Output is correct
12 Correct 194 ms 21808 KB Output is correct
13 Correct 244 ms 21844 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 13392 KB Output is correct
2 Correct 577 ms 31664 KB Output is correct
3 Correct 195 ms 25680 KB Output is correct
4 Correct 250 ms 16484 KB Output is correct
5 Correct 290 ms 16096 KB Output is correct
6 Correct 284 ms 15740 KB Output is correct
7 Correct 260 ms 15184 KB Output is correct
8 Correct 165 ms 13308 KB Output is correct
9 Correct 451 ms 33264 KB Output is correct
10 Correct 628 ms 31652 KB Output is correct
11 Correct 522 ms 29892 KB Output is correct
12 Correct 478 ms 29268 KB Output is correct
13 Correct 278 ms 31512 KB Output is correct
14 Correct 194 ms 25544 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 24104 KB Output is correct
2 Correct 612 ms 31056 KB Output is correct
3 Correct 374 ms 33764 KB Output is correct
4 Correct 270 ms 30724 KB Output is correct
5 Correct 399 ms 29524 KB Output is correct
6 Correct 364 ms 30392 KB Output is correct
7 Correct 354 ms 29012 KB Output is correct
8 Correct 453 ms 33924 KB Output is correct
9 Correct 470 ms 33268 KB Output is correct
10 Correct 620 ms 32852 KB Output is correct
11 Correct 625 ms 33616 KB Output is correct
12 Correct 600 ms 31068 KB Output is correct
13 Correct 596 ms 37224 KB Output is correct
14 Correct 267 ms 29360 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 492 ms 33524 KB Output is correct
2 Correct 565 ms 30608 KB Output is correct
3 Correct 289 ms 33916 KB Output is correct
4 Correct 529 ms 33572 KB Output is correct
5 Correct 764 ms 31716 KB Output is correct
6 Correct 498 ms 30008 KB Output is correct
7 Correct 664 ms 30556 KB Output is correct
8 Correct 294 ms 33924 KB Output is correct
9 Correct 214 ms 25648 KB Output is correct