oj.uz

Submission #872082

# Submission time Handle Problem Language Result Execution time Memory
872082 2023-11-12T09:25:03 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
7.53968 / 100
 1000 ms 36260 KB 
/*              IN THE NAME OF GOD              */
// Oh, let the bullets fly, oh, let them rain
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100'000, lg = 18;

bool is_filled[MAXN + 10];
int par_sp[MAXN + 10][lg + 10], order[MAXN + 10], mn[MAXN + 10], direct_par[MAXN + 10], n, q, tt;

vector<int> adj[MAXN + 10];
set<pair<int, int>> take_order;

void input();
void solve();
void dfs_get_minimum(int u, int par);
void dfs_get_order(int u, int par);
void par_spars_table();
int query1(int cnt);
int query2(int id);

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    input();
    solve();
    return 0;
}

void input() {
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> direct_par[i];
        direct_par[i]--;
        if (direct_par[i] == -1)
            continue;
        adj[direct_par[i]].push_back(i);
        adj[i].push_back(direct_par[i]);
    }
}

void solve() {
    dfs_get_minimum(0, -1);
    dfs_get_order(0, -1);
    par_spars_table();
    //cout << par_sp[7][2] << '\n';
    for (int i = 0; i < n; i++)
        take_order.insert({order[i], i});
    while (q--) {
        int type, x;
        cin >> type >> x;
        if (type == 1)
            cout << query1(x) + 1 << '\n';
        else  {
            x--;
            cout << query2(x) << '\n';
        }
    }
}

void dfs_get_minimum(int u, int par) {
    int res = u;
    for (int v : adj[u])
        if (v != par) {
            dfs_get_minimum(v, u);
            res = min(res, mn[v]);
        }
    mn[u] = res;
}

void dfs_get_order(int u, int par) {
    set<pair<int, int>> st;
    for (int v : adj[u])
        if (v != par)
            st.insert({mn[v], v});
    for (auto p : st)
        dfs_get_order(p.second, u);
    order[u] = tt++;
}

void par_spars_table() {
    for (int i = 0; i < n; i++)
        par_sp[i][0] = direct_par[i];
    for (int k = 1; k < lg; k++)
        for (int i = 0; i < n; i++) {
            if (par_sp[i][k - 1] == -1)
                par_sp[i][k] = -1;
        else
            par_sp[i][k] = par_sp[par_sp[i][k - 1]][k - 1];
        }
}

int query1(int cnt) {
    for (int i = 0; i < cnt; i++) {
        int u = (*take_order.begin()).second;
        is_filled[u] = true;
        take_order.erase(take_order.begin());
        if (i == cnt - 1)
            return u;
    }
}

int query2(int id) {
    int u = id, ans = 0;
    for (int k = lg - 1; k >= 0; k--) {
        if (par_sp[u][k] == -1)
            continue;
        if (is_filled[par_sp[u][k]] == true) {
            u = par_sp[u][k];
            ans += (1 << k);
        }
    }
    is_filled[u] = false;
    take_order.insert({order[u], u});
    return ans;
}

Compilation message

ballmachine.cpp: In function 'int query1(int)':
ballmachine.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
  100 | }
      | ^

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 6744 KB Time limit exceeded
2 Execution timed out 1037 ms 20048 KB Time limit exceeded
3 Incorrect 55 ms 20304 KB Output isn't correct
4 Execution timed out 1072 ms 6748 KB Time limit exceeded
5 Execution timed out 1076 ms 6748 KB Time limit exceeded
6 Incorrect 1 ms 6744 KB Output isn't correct
7 Execution timed out 1093 ms 6748 KB Time limit exceeded
8 Execution timed out 1037 ms 6744 KB Time limit exceeded
9 Execution timed out 1045 ms 7004 KB Time limit exceeded
10 Execution timed out 1053 ms 10076 KB Time limit exceeded
11 Execution timed out 1057 ms 20060 KB Time limit exceeded
12 Incorrect 53 ms 20308 KB Output isn't correct
13 Execution timed out 1039 ms 20172 KB Time limit exceeded

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12888 KB Output is correct
2 Incorrect 120 ms 28140 KB Output isn't correct
3 Incorrect 70 ms 23392 KB Output isn't correct
4 Execution timed out 1050 ms 15684 KB Time limit exceeded
5 Execution timed out 1080 ms 15192 KB Time limit exceeded
6 Incorrect 53 ms 15860 KB Output isn't correct
7 Execution timed out 1094 ms 14560 KB Time limit exceeded
8 Correct 27 ms 12888 KB Output is correct
9 Incorrect 126 ms 30844 KB Output isn't correct
10 Incorrect 151 ms 28012 KB Output isn't correct
11 Incorrect 142 ms 28556 KB Output isn't correct
12 Execution timed out 1059 ms 28764 KB Time limit exceeded
13 Correct 76 ms 32688 KB Output is correct
14 Incorrect 67 ms 23212 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 19792 KB Output isn't correct
2 Incorrect 171 ms 28244 KB Output isn't correct
3 Incorrect 108 ms 30804 KB Output isn't correct
4 Incorrect 98 ms 27712 KB Output isn't correct
5 Incorrect 84 ms 25812 KB Output isn't correct
6 Incorrect 81 ms 27152 KB Output isn't correct
7 Incorrect 93 ms 25168 KB Output isn't correct
8 Incorrect 106 ms 30808 KB Output isn't correct
9 Incorrect 169 ms 30996 KB Output isn't correct
10 Incorrect 168 ms 28024 KB Output isn't correct
11 Incorrect 151 ms 30040 KB Output isn't correct
12 Incorrect 155 ms 28392 KB Output isn't correct
13 Incorrect 161 ms 36260 KB Output isn't correct
14 Incorrect 129 ms 23088 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 31300 KB Output isn't correct
2 Incorrect 135 ms 27284 KB Output isn't correct
3 Correct 139 ms 34592 KB Output is correct
4 Incorrect 187 ms 31192 KB Output isn't correct
5 Incorrect 193 ms 27520 KB Output isn't correct
6 Incorrect 118 ms 28852 KB Output isn't correct
7 Incorrect 151 ms 27392 KB Output isn't correct
8 Correct 118 ms 34408 KB Output is correct
9 Incorrect 86 ms 23212 KB Output isn't correct