oj.uz

Submission #666275

# Submission time Handle Problem Language Result Execution time Memory
666275 2022-11-28T04:05:10 Z vuavisao Ball Machine (BOI13_ballmachine) C++14
100 / 100
 186 ms 24312 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;

template<typename Lhs, typename Rhs> inline void Max_self(Lhs &a, Rhs b) { a = (a > b ? a : b); }
template<typename Lhs, typename Rhs> inline void Min_self(Lhs &a, Rhs b) { a = (a < b ? a : b); }

const int N = 1e5 + 10;

void dfs_more_and_more(int u);
void dfs_calc(int u);
void pre_calc();
int first_parent(int u);

int n, q;
vector<int> g[N];

int root;
int Lg, dist[N], parent[20][N];

bool have[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int cnt, in[N];
int dp[N];

void dfs_more_and_more(int u) {
    dp[u] = u;
    for(auto v : g[u]) {
        dist[v] = dist[u] + 1;
        parent[0][v] = u;
        dfs_more_and_more(v);
        Min_self(dp[u], dp[v]);
    }
}

void dfs_calc(int u) {
    sort(g[u].begin(), g[u].end(), [&] (int lhs, int rhs) {
        if(dp[lhs] != dp[rhs]) return dp[lhs] < dp[rhs];
        return lhs < rhs;
    });
    for(auto v : g[u]) dfs_calc(v);
    in[u] = ++ cnt;
    pq.push(make_pair(in[u], u));
}

int first_parent(int u) {
    for(int i = Lg; i >= 0; -- i)
        if(have[parent[i][u]] & 1) u = parent[i][u];
    return u;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("Ball.inp", "r")) {
        freopen("Ball.inp", "r", stdin);
        freopen("Ball.out", "w", stdout);
    }
    cin >> n >> q;
    for(int v = 1; v <= n; ++ v) {
        int u; cin >> u;
        if(u == 0) root = v;
        else g[u].push_back(v);
//        cout << u << ' ' << v << '\n';
    }
    pre_calc();
    while(q--) {
        int type; cin >> type;
        if(type == 1) {
            int k; cin >> k;
            while(k--) {
                auto psy = pq.top(); pq.pop();
                have[psy.second] = true;
                if(k == 0) cout << psy.second;
            }
        }
        else {
            int u; cin >> u;
            int p = first_parent(u);
            have[p] = false;
            pq.push(make_pair(in[p], p));
//            cout << u << ' ' << p << ' ';
            cout << dist[u] - dist[p];
        }
        cout << '\n';
    }
    return 0;
}

void pre_calc() {
    dfs_more_and_more(root);
    dfs_calc(root);

    Lg = __lg(n);
    for(int j = 1; j <= Lg; ++ j)
        for(int i = 1; i <= n; ++ i)
            parent[j][i] = parent[j - 1][parent[j - 1][i]];
}

/// Code by vuavisao

Compilation message

ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen("Ball.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen("Ball.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 141 ms 10628 KB Output is correct
3 Correct 41 ms 10564 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2684 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 3 ms 2820 KB Output is correct
9 Correct 9 ms 3156 KB Output is correct
10 Correct 16 ms 4616 KB Output is correct
11 Correct 90 ms 10580 KB Output is correct
12 Correct 44 ms 10564 KB Output is correct
13 Correct 87 ms 10660 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7052 KB Output is correct
2 Correct 186 ms 18804 KB Output is correct
3 Correct 56 ms 14016 KB Output is correct
4 Correct 58 ms 8044 KB Output is correct
5 Correct 56 ms 7924 KB Output is correct
6 Correct 55 ms 7848 KB Output is correct
7 Correct 59 ms 7052 KB Output is correct
8 Correct 26 ms 7056 KB Output is correct
9 Correct 152 ms 19264 KB Output is correct
10 Correct 157 ms 18916 KB Output is correct
11 Correct 143 ms 19068 KB Output is correct
12 Correct 153 ms 16736 KB Output is correct
13 Correct 65 ms 21572 KB Output is correct
14 Correct 56 ms 13996 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 11104 KB Output is correct
2 Correct 148 ms 17024 KB Output is correct
3 Correct 88 ms 19776 KB Output is correct
4 Correct 80 ms 15988 KB Output is correct
5 Correct 91 ms 15648 KB Output is correct
6 Correct 78 ms 15584 KB Output is correct
7 Correct 80 ms 14096 KB Output is correct
8 Correct 78 ms 19752 KB Output is correct
9 Correct 136 ms 19516 KB Output is correct
10 Correct 143 ms 19028 KB Output is correct
11 Correct 180 ms 19052 KB Output is correct
12 Correct 147 ms 17088 KB Output is correct
13 Correct 160 ms 24312 KB Output is correct
14 Correct 134 ms 14528 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 19512 KB Output is correct
2 Correct 185 ms 17096 KB Output is correct
3 Correct 72 ms 23880 KB Output is correct
4 Correct 139 ms 19520 KB Output is correct
5 Correct 153 ms 19136 KB Output is correct
6 Correct 120 ms 19012 KB Output is correct
7 Correct 141 ms 17096 KB Output is correct
8 Correct 69 ms 23864 KB Output is correct
9 Correct 61 ms 14004 KB Output is correct