oj.uz

Submission #551811

# Submission time Handle Problem Language Result Execution time Memory
551811 2022-04-21T15:29:48 Z Vladth11 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 230 ms 34080 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 100001;
const ll VMAX = 1001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 31;
const ll nr_of_bits = 21;

class AIB{
public:
    int aib[NMAX + 1];
    void update(int x, int val){
        for(; x < NMAX; x += x&(-x))
            aib[x] += val;
    }
    int query(int x){
        int val = 0;
        for(; x > 0; x -= x&(-x))
            val += aib[x];
        return val;
    }
    int first(){
        int r = 0, pas = (1 << nr_of_bits), sum = 0;
        while(pas){
            if(r + pas < NMAX && sum + aib[r + pas] == r + pas){
                r += pas;
                sum += aib[r];
            }
            pas /= 2;
        }
        if(sum == r)
            r++;
        return r;
    }
}aib, primul;

vector <int> v[NMAX];
pii timp[NMAX];
int stamp = 0;
int dp[NMAX][nr_of_bits + 1];
int minim[NMAX];
int lvl[NMAX];

void DFS(int node, int p){
    minim[node] = node;
    lvl[node] = lvl[p] + 1;
    dp[node][0] = p;
    timp[node].first = ++stamp;
    for(auto x : v[node]){
        if(x == p)
            continue;
        DFS(x, node);
        minim[node] = min(minim[node], minim[x]);
    }
    timp[node].second = stamp;
}

int order[NMAX];
int cnt = 0;

bool cmp(int a, int b){
    return minim[a] < minim[b];
}
int f[NMAX];

void baga(int node, int p){
    vector <int> cv;
    for(auto x : v[node]){
        if(x == p) continue;
        cv.push_back(x);
    }
    sort(cv.begin(), cv.end(), cmp);
    for(auto x : cv){
        baga(x, node);
    }
    order[++cnt] = node;
    f[node] = cnt;
}

int taken[NMAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q, i, root;
    cin >> n >> q;
    for(i = 1; i <= n; i++){
        int x;
        cin >> x;
        if(x == 0){
            root = i;
        }else{
            v[x].push_back(i);
            v[i].push_back(x);
        }
    }
    DFS(root, 0);
    for(int j = 1; j <= nr_of_bits; j++){
        for(i = 1; i <= n; i++){
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
    baga(root, 0);
    while(q--){
        int t, x;
        cin >> t >> x;
        if(t == 1){
            int ultim = 0;
            while(x--){
                int unde = primul.first();
                int cine = order[unde];
                ultim = cine;
                primul.update(unde, 1);
                taken[cine] = 1;
                aib.update(timp[cine].first, 1);
                aib.update(timp[cine].second + 1, -1);
            }
            cout << ultim << "\n";
        }else{
            int r = x, pas = nr_of_bits, cate = aib.query(timp[x].first);
            while(pas >= 0){
                int nxt = dp[r][pas];
                int diferenta = lvl[x] - lvl[nxt];
                if(nxt != 0 && aib.query(timp[nxt].first) + diferenta == cate && taken[nxt])
                    r = nxt;
                pas--;
            }
            primul.update(f[r], -1);
            taken[r] = 0;
            aib.update(timp[r].first, -1);
            aib.update(timp[r].second + 1, 1);
            cout << lvl[x] - lvl[r] << "\n";
        }
    }
    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:113:9: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     baga(root, 0);
      |     ~~~~^~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 94 ms 12820 KB Output is correct
3 Correct 60 ms 12364 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2900 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 3 ms 2832 KB Output is correct
9 Correct 7 ms 3284 KB Output is correct
10 Correct 20 ms 5272 KB Output is correct
11 Correct 101 ms 12792 KB Output is correct
12 Correct 61 ms 12364 KB Output is correct
13 Correct 94 ms 12372 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 8376 KB Output is correct
2 Correct 205 ms 25688 KB Output is correct
3 Correct 81 ms 17204 KB Output is correct
4 Correct 91 ms 9684 KB Output is correct
5 Correct 85 ms 9680 KB Output is correct
6 Correct 76 ms 9488 KB Output is correct
7 Correct 73 ms 8076 KB Output is correct
8 Correct 44 ms 8420 KB Output is correct
9 Correct 166 ms 25668 KB Output is correct
10 Correct 185 ms 25676 KB Output is correct
11 Correct 164 ms 25404 KB Output is correct
12 Correct 181 ms 21248 KB Output is correct
13 Correct 129 ms 29384 KB Output is correct
14 Correct 81 ms 17304 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 14388 KB Output is correct
2 Correct 207 ms 22260 KB Output is correct
3 Correct 172 ms 27572 KB Output is correct
4 Correct 109 ms 21256 KB Output is correct
5 Correct 128 ms 21216 KB Output is correct
6 Correct 143 ms 21264 KB Output is correct
7 Correct 116 ms 18116 KB Output is correct
8 Correct 122 ms 27572 KB Output is correct
9 Correct 207 ms 26132 KB Output is correct
10 Correct 195 ms 26076 KB Output is correct
11 Correct 181 ms 26048 KB Output is correct
12 Correct 230 ms 22228 KB Output is correct
13 Correct 201 ms 34080 KB Output is correct
14 Correct 111 ms 18372 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 25860 KB Output is correct
2 Correct 209 ms 22028 KB Output is correct
3 Correct 115 ms 32796 KB Output is correct
4 Correct 215 ms 25952 KB Output is correct
5 Correct 228 ms 25760 KB Output is correct
6 Correct 162 ms 25288 KB Output is correct
7 Correct 199 ms 22012 KB Output is correct
8 Correct 129 ms 32844 KB Output is correct
9 Correct 78 ms 17280 KB Output is correct