oj.uz

Submission #677663

# Submission time Handle Problem Language Result Execution time Memory
677663 2023-01-04T06:38:06 Z dooompy Ball Machine (BOI13_ballmachine) C++17
82.619 / 100
 1000 ms 37168 KB 
#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

vector<int> adj[100005];
int jmp[100005][20];
int depth[100005];
vector<int> trav;
bool seen[100005];
map<int, int> fromp, fromv;
int mn[100005];

void dfs(int node, int par = -1) {

    if (!seen[node]) {
        seen[node] = true;
        trav.push_back(node);
    }
    for (int i = 1; i < 20; i++) {
        jmp[node][i] = jmp[jmp[node][i-1]][i-1];
    }

    for (auto nxt : adj[node]) {
        depth[nxt] = depth[node] + 1;
        jmp[nxt][0] = node;
        dfs(nxt, node);
    }
}

void dfs2(int node) {
    mn[node] = node;

    for (auto nxt : adj[node]) {
        dfs2(nxt);

        mn[node] = min(mn[node], mn[nxt]);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("test.txt", "r", stdin);
//    freopen("", "w", stdout);
    int n, q; cin >> n >> q;
    int root = 0;
    for (int i = 1; i <= n; i++) {
        int t; cin >> t;
        if (t == 0) {
            root = i;
            continue;
        }
        adj[t].push_back(i);
    }

    dfs2(root);


    for (int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end(), [](int a, int b) {
            return mn[a] > mn[b];
        });
    }


    jmp[root][0] = 1;
    depth[root] = 1;
    dfs(root);

    reverse(trav.begin(), trav.end());

//    for (auto a : trav) cout << a << " ";

    set<int> st;
    for (int i = 1; i <= n; i++) {
        fromp[i] = trav[i - 1];
        fromv[trav[i-1]] = i;
        st.insert(i);
    }

//    for (auto x: trav) cout << x << " ";
//    cout << endl;
//    cout << fromp[184] << " " << fromp[185] << " " << fromp[183] << endl;
//    cout << fromv[212] << endl;

    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b;

        if (a == 1) {
            // add

            int lst = -1;
            while (b) {
                auto addedto = *st.begin();
                st.erase(addedto);

                lst = fromp[addedto];
                b--;
            }

            cout << lst << "\n";
        } else {
            // remove node b

            int tempb = b;
            int dist = 0;

            for (int i = 19; i >= 0; i--) {
                int jmpto = jmp[tempb][i];

                if (st.count(fromv[jmpto]) || depth[tempb] - (1 << i) < 1) {
                    continue;
                }


                dist += (1 << i);
                tempb = jmp[tempb][i];
            }

            int idx = fromv[tempb];
            st.insert(idx);
            cout << dist << "\n";
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 415 ms 20240 KB Output is correct
3 Correct 144 ms 20220 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2728 KB Output is correct
6 Correct 3 ms 2900 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 4 ms 2900 KB Output is correct
9 Correct 19 ms 3696 KB Output is correct
10 Correct 56 ms 6984 KB Output is correct
11 Correct 414 ms 20308 KB Output is correct
12 Correct 140 ms 20168 KB Output is correct
13 Correct 322 ms 20244 KB Output is correct

Subtask #2
25.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 9352 KB Output is correct
2 Execution timed out 1059 ms 32452 KB Time limit exceeded
3 Correct 211 ms 28316 KB Output is correct
4 Correct 313 ms 12140 KB Output is correct
5 Correct 419 ms 12048 KB Output is correct
6 Correct 386 ms 12024 KB Output is correct
7 Correct 366 ms 10936 KB Output is correct
8 Correct 85 ms 9648 KB Output is correct
9 Correct 773 ms 32896 KB Output is correct
10 Execution timed out 1042 ms 32448 KB Time limit exceeded
11 Correct 817 ms 32472 KB Output is correct
12 Correct 893 ms 30372 KB Output is correct
13 Correct 233 ms 32840 KB Output is correct
14 Correct 208 ms 28296 KB Output is correct

Subtask #3
28.5714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 17792 KB Output is correct
2 Execution timed out 1054 ms 31024 KB Time limit exceeded
3 Correct 598 ms 30048 KB Output is correct
4 Correct 429 ms 26772 KB Output is correct
5 Correct 634 ms 26436 KB Output is correct
6 Correct 651 ms 26352 KB Output is correct
7 Correct 635 ms 25164 KB Output is correct
8 Correct 562 ms 29988 KB Output is correct
9 Correct 779 ms 33060 KB Output is correct
10 Execution timed out 1086 ms 32656 KB Time limit exceeded
11 Execution timed out 1089 ms 32776 KB Time limit exceeded
12 Execution timed out 1087 ms 31032 KB Time limit exceeded
13 Correct 1000 ms 37168 KB Output is correct
14 Correct 371 ms 28736 KB Output is correct

Subtask #4
3.33333333333 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 33100 KB Output is correct
2 Execution timed out 1057 ms 31252 KB Time limit exceeded
3 Correct 268 ms 36780 KB Output is correct
4 Correct 801 ms 33156 KB Output is correct
5 Execution timed out 1091 ms 32540 KB Time limit exceeded
6 Correct 863 ms 32548 KB Output is correct
7 Execution timed out 1051 ms 30976 KB Time limit exceeded
8 Correct 275 ms 36756 KB Output is correct
9 Correct 198 ms 28392 KB Output is correct