oj.uz

답안 #196843

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
196843 2020-01-17T08:45:20 Z dantoh000 Ball Machine (BOI13_ballmachine) C++14
16.2271 / 100
 379 ms 20196 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n,q;
vector<int> adjlist[N];
int ct = 0;
int p[N][17];
int d[N];
int sz[N], mn[N], l[N], r[N],pos[N];
int fw[N];
vector<int> id;
int root;
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 dfs(int u){
    sz[u] = 1;
    mn[u] = u;
    for (auto v : adjlist[u]){
        d[v] = d[u]+1;
        for (int k = 1; k < 17; k++){
            p[v][k] = p[p[v][k-1]][k-1];
            if (p[v][k] == 0) break;
        }
        dfs(v);
        sz[u] += sz[v];
        mn[u] = min(mn[u],mn[v]);
    }
    return;
}
void visit(int u){
    l[u] = ++ct;
    for (auto v : adjlist[u]){
        if (mn[v] == mn[u]) visit(v);
    }
    for (auto v : adjlist[u]){
        if (mn[v] != mn[u]) visit(v);
    }
    id.push_back(u);
    r[u] = ct;
}
bool isempty(int x) {
    return sum(l[x],r[x]) != sz[x];
}
int add(){
    int lo = 1, hi = n;
    while (lo + 1 < hi){
        int mid = (lo+hi)/2;
        //printf("testing %d %d %d\n",id[mid],sum(id[mid]),mid);
        if (sum(id[mid]) != mid) hi = mid;
        else lo = mid;
    }
    if (lo + 1 == hi){
        //printf("testing %d %d %d\n",id[lo],sum(id[lo]),lo);
        if (sum(id[lo]) != lo) hi = lo;
        else lo = hi;
    }
    up(id[hi],1);
    return id[hi];
}
int rem(int x){
    for (int k = 16; k >= 0; k--){
        if (p[x][k] && !isempty(p[x][k])){
            x = p[x][k];
        }
    }
    up(x,-1);
    return x;
}
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;
        adjlist[p[i][0]].push_back(i);
    }
    id.push_back(0);
    dfs(root);
    visit(root);
    for (int i = 0; i < q; i++){
        int t,x;
        scanf("%d%d",&t,&x);
        if (t == 1){
            int last;
            for (int i = 0; i < x; i++){
                last = add();
                //printf("added %d %d\n",i,last);
            }
            printf("%d\n",last);
        }
        else printf("%d\n",d[x]-d[rem(x)]);
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:85: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:87: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:96: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
3.84615384615 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2680 KB Output isn't correct
2 Incorrect 137 ms 10232 KB Output isn't correct
3 Correct 84 ms 10260 KB Output is correct
4 Incorrect 4 ms 2680 KB Output isn't correct
5 Incorrect 4 ms 2808 KB Output isn't correct
6 Incorrect 5 ms 2808 KB Output isn't correct
7 Incorrect 5 ms 2808 KB Output isn't correct
8 Incorrect 5 ms 2808 KB Output isn't correct
9 Incorrect 12 ms 3196 KB Output isn't correct
10 Incorrect 28 ms 4728 KB Output isn't correct
11 Incorrect 140 ms 10212 KB Output isn't correct
12 Correct 88 ms 10232 KB Output is correct
13 Incorrect 113 ms 10232 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 6136 KB Output is correct
2 Incorrect 336 ms 16800 KB Output isn't correct
3 Correct 93 ms 13680 KB Output is correct
4 Incorrect 107 ms 7288 KB Output isn't correct
5 Incorrect 139 ms 7032 KB Output isn't correct
6 Incorrect 130 ms 7032 KB Output isn't correct
7 Incorrect 123 ms 6648 KB Output isn't correct
8 Correct 59 ms 6264 KB Output is correct
9 Incorrect 237 ms 17172 KB Output isn't correct
10 Incorrect 318 ms 16800 KB Output isn't correct
11 Incorrect 301 ms 16756 KB Output isn't correct
12 Incorrect 266 ms 15344 KB Output isn't correct
13 Correct 165 ms 18132 KB Output is correct
14 Correct 90 ms 13464 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 99 ms 9972 KB Output isn't correct
2 Incorrect 285 ms 15544 KB Output isn't correct
3 Incorrect 189 ms 16752 KB Output isn't correct
4 Incorrect 180 ms 14452 KB Output isn't correct
5 Incorrect 231 ms 13840 KB Output isn't correct
6 Incorrect 230 ms 13948 KB Output isn't correct
7 Incorrect 237 ms 13072 KB Output isn't correct
8 Incorrect 246 ms 16752 KB Output isn't correct
9 Incorrect 295 ms 17180 KB Output isn't correct
10 Incorrect 365 ms 16752 KB Output isn't correct
11 Incorrect 362 ms 16788 KB Output isn't correct
12 Incorrect 344 ms 15604 KB Output isn't correct
13 Incorrect 379 ms 20196 KB Output isn't correct
14 Incorrect 160 ms 13908 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 321 ms 17204 KB Output isn't correct
2 Incorrect 352 ms 15572 KB Output isn't correct
3 Correct 234 ms 20084 KB Output is correct
4 Incorrect 338 ms 17260 KB Output isn't correct
5 Incorrect 351 ms 16756 KB Output isn't correct
6 Incorrect 272 ms 16752 KB Output isn't correct
7 Incorrect 343 ms 15600 KB Output isn't correct
8 Correct 233 ms 20080 KB Output is correct
9 Correct 112 ms 13428 KB Output is correct