oj.uz

Submission #755476

# Submission time Handle Problem Language Result Execution time Memory
755476 2023-06-10T07:06:06 Z dxz05 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 308 ms 26016 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 1e5 + 3e2;

int p[N];
vector<int> g[N];

int sub_min[N];
const int L = 17;
int up[N][L];

void dfs0(int v){
    up[v][0] = p[v];
    for (int i = 1; i < L; i++) up[v][i] = up[up[v][i - 1]][i - 1];

    sub_min[v] = v;
    for (int u : g[v]){
        dfs0(u);
        sub_min[v] = min(sub_min[v], sub_min[u]);
    }
}

int order[N], vertex[N];
int timer = 0;

void traversal(int v){
    sort(all(g[v]), [&](int x, int y){
        return sub_min[x] < sub_min[y];
    });

    for (int u : g[v]) traversal(u);

    timer++;
    order[v] = timer;
    vertex[timer] = v;
}

bool flag[N];

void solve(){
    int n, q;
    cin >> n >> q;

    int root = 0;
    for (int i = 1; i <= n; i++){
        cin >> p[i];
        if (p[i] != 0){
            g[p[i]].push_back(i);
        } else {
            root = i;
        }
    }

    dfs0(root);
    traversal(root);

    set<int> free;
    for (int i = 1; i <= n; i++) free.insert(i);

    while (q--){
        int t;
        cin >> t;
        if (t == 1){
            int k;
            cin >> k;

            int last = 0;
            while (k--){
                int v = *free.begin();
                free.erase(free.begin());
                v = vertex[v];
                flag[v] = true;
                last = v;
            }

            cout << last << endl;
        } else {
            int v;
            cin >> v;

            int cnt = 0;
            for (int i = L - 1; i >= 0; i--){
                int x = up[v][i];
                if (x != 0 && flag[x]){
                    v = x;
                    cnt += 1 << i;
                }
            }

            free.insert(order[v]);
            flag[v] = false;

            cout << cnt << endl;
        }
    }

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:116:13: warning: unused variable 'startTime' [-Wunused-variable]
  116 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 211 ms 12412 KB Output is correct
3 Correct 172 ms 12640 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 5 ms 2772 KB Output is correct
7 Correct 5 ms 2772 KB Output is correct
8 Correct 4 ms 2772 KB Output is correct
9 Correct 17 ms 3328 KB Output is correct
10 Correct 43 ms 5112 KB Output is correct
11 Correct 229 ms 12408 KB Output is correct
12 Correct 207 ms 12624 KB Output is correct
13 Correct 197 ms 12444 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 6968 KB Output is correct
2 Correct 258 ms 21032 KB Output is correct
3 Correct 182 ms 17124 KB Output is correct
4 Correct 163 ms 8424 KB Output is correct
5 Correct 145 ms 8148 KB Output is correct
6 Correct 146 ms 8280 KB Output is correct
7 Correct 143 ms 7316 KB Output is correct
8 Correct 116 ms 6944 KB Output is correct
9 Correct 265 ms 21560 KB Output is correct
10 Correct 245 ms 20828 KB Output is correct
11 Correct 244 ms 20888 KB Output is correct
12 Correct 247 ms 18920 KB Output is correct
13 Correct 214 ms 22784 KB Output is correct
14 Correct 186 ms 17116 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 12200 KB Output is correct
2 Correct 289 ms 19912 KB Output is correct
3 Correct 178 ms 21240 KB Output is correct
4 Correct 178 ms 18124 KB Output is correct
5 Correct 167 ms 17460 KB Output is correct
6 Correct 168 ms 17464 KB Output is correct
7 Correct 202 ms 16036 KB Output is correct
8 Correct 170 ms 21324 KB Output is correct
9 Correct 268 ms 21972 KB Output is correct
10 Correct 291 ms 21724 KB Output is correct
11 Correct 305 ms 21596 KB Output is correct
12 Correct 290 ms 20068 KB Output is correct
13 Correct 308 ms 26016 KB Output is correct
14 Correct 250 ms 17256 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 22244 KB Output is correct
2 Correct 278 ms 19916 KB Output is correct
3 Correct 227 ms 25276 KB Output is correct
4 Correct 286 ms 21976 KB Output is correct
5 Correct 293 ms 21416 KB Output is correct
6 Correct 233 ms 21024 KB Output is correct
7 Correct 272 ms 20076 KB Output is correct
8 Correct 226 ms 25272 KB Output is correct
9 Correct 193 ms 17276 KB Output is correct