oj.uz

답안 #196883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
196883 2020-01-17T13:10:17 Z dantoh000 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 338 ms 26160 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n,q;
vector<int> adjlist[N];
int ct = 1;
int p[N][20];
int d[N], mn[N], l[N], r[N], pos[N];
int fw[N], id[N];
int root;
bool cmp(int x, int y){
    return mn[x] < mn[y];
}
void up(int x, int v){
    while (x <= N){
        fw[x] += v;
        x += x&(-x);
    }
}
int sum(int x){
    int res = 0;
    while (x){
        res += fw[x];
        x -= x&(-x);
    }
    return res;
}
int sum(int s, int e){
    return sum(e)-sum(s-1);
}
void print(){ for (int i = 1; i <= n; i++) printf("%d ",sum(i,i)); printf("\n");}
void dfs(int u){
    mn[u] = u;
    for (auto v : adjlist[u]){
        d[v] = d[u]+1;
        for (int k = 1; k < 20; k++){
            p[v][k] = p[p[v][k-1]][k-1];
            if (p[v][k] == 0) break;
        }
        dfs(v);
        mn[u] = min(mn[u],mn[v]);
    }
    return;
}
void visit(int u){
    l[u] = ct;
    sort(adjlist[u].begin(),adjlist[u].end(),cmp);
    for (auto v : adjlist[u]){
        visit(v);
    }
    id[ct] = u;
    pos[u] = ct;
    r[u] = ct++;
}
int add(){
    int lo = 0, hi = n;
    while (lo + 1 < hi){
        int mid = (lo+hi)/2;
        if (sum(mid) != mid) hi = mid;
        else lo = mid;
    }
    up(lo+1,1);
    ///print();
    return id[lo+1];
}
int rem(int x){
    int ans = 0;
    for (int k = 19; k >= 0; k--){
        int P = p[x][k];
        if (P && sum(l[P],r[P]) == r[P]-l[P]+1){
            x = P;
            ans |= (1<<k);
        }
    }
    up(pos[x],-1);
    ///print();
    return ans;
}
int main(){
    scanf("%d%d",&n,&q);
    for (int i = 1; i <= n; i++){
        scanf("%d",&p[i][0]);
        if (p[i][0] == 0) root = i;
        else adjlist[p[i][0]].push_back(i);
    }
    dfs(root);
    visit(root);
    for (int i = 0; i < q; i++){
        int t,x;
        scanf("%d%d",&t,&x);
        if (t == 1){
            int last;
            while (x--){
                last = add();
                //printf("added %d %d\n",i,last);
            }
            printf("%d\n",last);
        }
        else {
            printf("%d\n",rem(x));
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~
ballmachine.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[i][0]);
         ~~~~~^~~~~~~~~~~~~~~
ballmachine.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&t,&x);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 142 ms 12004 KB Output is correct
3 Correct 82 ms 11928 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2848 KB Output is correct
9 Correct 11 ms 3448 KB Output is correct
10 Correct 29 ms 4984 KB Output is correct
11 Correct 135 ms 11896 KB Output is correct
12 Correct 80 ms 11792 KB Output is correct
13 Correct 123 ms 11680 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 7540 KB Output is correct
2 Correct 253 ms 20444 KB Output is correct
3 Correct 92 ms 15476 KB Output is correct
4 Correct 104 ms 8760 KB Output is correct
5 Correct 115 ms 8772 KB Output is correct
6 Correct 115 ms 8496 KB Output is correct
7 Correct 120 ms 7544 KB Output is correct
8 Correct 48 ms 7416 KB Output is correct
9 Correct 202 ms 21060 KB Output is correct
10 Correct 329 ms 20472 KB Output is correct
11 Correct 218 ms 20344 KB Output is correct
12 Correct 245 ms 18188 KB Output is correct
13 Correct 194 ms 22904 KB Output is correct
14 Correct 92 ms 15364 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 11988 KB Output is correct
2 Correct 257 ms 18840 KB Output is correct
3 Correct 177 ms 21112 KB Output is correct
4 Correct 169 ms 17404 KB Output is correct
5 Correct 172 ms 16876 KB Output is correct
6 Correct 177 ms 16888 KB Output is correct
7 Correct 166 ms 15352 KB Output is correct
8 Correct 186 ms 21116 KB Output is correct
9 Correct 304 ms 21368 KB Output is correct
10 Correct 338 ms 20900 KB Output is correct
11 Correct 318 ms 20904 KB Output is correct
12 Correct 242 ms 18808 KB Output is correct
13 Correct 275 ms 26160 KB Output is correct
14 Correct 150 ms 16116 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 260 ms 21240 KB Output is correct
2 Correct 265 ms 18784 KB Output is correct
3 Correct 165 ms 25500 KB Output is correct
4 Correct 252 ms 21224 KB Output is correct
5 Correct 266 ms 19824 KB Output is correct
6 Correct 213 ms 19536 KB Output is correct
7 Correct 249 ms 18012 KB Output is correct
8 Correct 161 ms 24824 KB Output is correct
9 Correct 93 ms 14968 KB Output is correct