oj.uz

Submission #385611

# Submission time Handle Problem Language Result Execution time Memory
385611 2021-04-04T16:04:02 Z vishesh312 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 293 ms 39788 KB 
#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()

using ll = long long;
const int mod = 1e9+7;

vector<vector<int>> adj, up;
vector<int> par, submn, tout, depth;
vector<bool> boulder;
set<pair<int, int>> s;
int LOG = 0, timer = 0;

void dfs1(int u, int p = -1) {
    submn[u] = u;
    for (int v : adj[u]) {
        if (v != p) {
            depth[v] = depth[u] + 1;
            dfs1(v, u);
            submn[u] = min(submn[u], submn[v]);
        }
    }
}

void dfs2(int u, int p = -1) {
    set<pair<int, int>> curs;
    for (int v : adj[u]) {
        if (v != p) {
            curs.insert({submn[v], v});
        }
    }
    for (auto pr : curs) {
        dfs2(pr.second, u);
    }
    tout[u] = ++timer;
    s.insert({tout[u], u});
}

void solve(int tc) {
    int n, q;
    cin >> n >> q;
    boulder.resize(n); adj.resize(n); up.resize(n); submn.resize(n); tout.resize(n); par.resize(n); depth.resize(n);
    int root = -1;
    while ((1 << LOG) <= n) ++LOG;
    for (auto &x : up) x.resize(LOG);
    for (int i = 0; i < n; ++i) {
        int p;
        cin >> p;
        if (p == 0) {
            root = i;
            continue;
        }
        --p;
        par[i] = p;
        adj[p].push_back(i);
        adj[i].push_back(p);
    }
    for (int i = 0; i < n; ++i) up[i][0] = par[i];
    up[root][0] = root;
    for (int l = 1; l < LOG; ++l) {
        for (int i = 0; i < n; ++i) {
            up[i][l] = up[up[i][l-1]][l-1];
        }
    }
    dfs1(root);
    dfs2(root);
    while (q--) {
        int a, b;
        cin >> a >> b;
//      cerr << "a b : " << a << " " << b << '\n';
        if (a == 1) {
            pair<int, int> cur;
            for (int i = 0; i < b; ++i) {
                cur = *s.begin();
                auto it = s.begin();
                s.erase(it);
                boulder[cur.second] = true;
            }
            cout << cur.second+1 << '\n';
        } else {
            --b;
            int cur = LOG-1;
            int dist = 0;
            while (cur >= 0) {
                if (depth[b] >= (1<<cur) and boulder[up[b][cur]]) {
//                  cout << "b cur up[b][cur] : " << b << " " << cur << " " << up[b][cur] << '\n';
                    b = up[b][cur];
                    dist ^= (1<<cur);
//                  cout << "b : " << b << '\n';
                }
                --cur;
            }
            s.insert({tout[b], b});
            boulder[b] = false;
            cout << dist << '\n';
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int tc = 1;
    //cin >> tc;
    for (int i = 1; i <= tc; ++i) solve(i);
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 152 ms 16108 KB Output is correct
3 Correct 128 ms 16108 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 8 ms 1260 KB Output is correct
10 Correct 27 ms 3948 KB Output is correct
11 Correct 167 ms 16108 KB Output is correct
12 Correct 111 ms 16108 KB Output is correct
13 Correct 160 ms 16096 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8044 KB Output is correct
2 Correct 230 ms 31596 KB Output is correct
3 Correct 137 ms 25960 KB Output is correct
4 Correct 78 ms 10220 KB Output is correct
5 Correct 79 ms 10092 KB Output is correct
6 Correct 69 ms 10220 KB Output is correct
7 Correct 74 ms 8428 KB Output is correct
8 Correct 42 ms 8044 KB Output is correct
9 Correct 215 ms 31724 KB Output is correct
10 Correct 251 ms 31804 KB Output is correct
11 Correct 197 ms 31596 KB Output is correct
12 Correct 212 ms 27116 KB Output is correct
13 Correct 162 ms 35180 KB Output is correct
14 Correct 174 ms 25960 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 16108 KB Output is correct
2 Correct 281 ms 27880 KB Output is correct
3 Correct 203 ms 31724 KB Output is correct
4 Correct 172 ms 25328 KB Output is correct
5 Correct 168 ms 25324 KB Output is correct
6 Correct 167 ms 25324 KB Output is correct
7 Correct 176 ms 22124 KB Output is correct
8 Correct 189 ms 31724 KB Output is correct
9 Correct 274 ms 31852 KB Output is correct
10 Correct 280 ms 31980 KB Output is correct
11 Correct 265 ms 31868 KB Output is correct
12 Correct 287 ms 28140 KB Output is correct
13 Correct 293 ms 39788 KB Output is correct
14 Correct 254 ms 26344 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 32120 KB Output is correct
2 Correct 276 ms 27924 KB Output is correct
3 Correct 190 ms 39532 KB Output is correct
4 Correct 272 ms 32004 KB Output is correct
5 Correct 282 ms 31980 KB Output is correct
6 Correct 224 ms 31852 KB Output is correct
7 Correct 286 ms 28140 KB Output is correct
8 Correct 208 ms 39532 KB Output is correct
9 Correct 145 ms 26088 KB Output is correct