oj.uz

답안 #385937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
385937 2021-04-05T09:05:54 Z arujbansal Ball Machine (BOI13_ballmachine) C++17
17.6984 / 100
 1000 ms 28648 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long

const int MXN = 1e5 + 5, INF = 1e9 + 5;
vector<int> adj[MXN];
int par[MXN], tin[MXN], tour[MXN], depth[MXN], valid[MXN], tout[MXN], present[MXN];
int timer, root;
priority_queue<int, vector<int>, greater<>> pq;
set<int> st;

int dfs(int u, int p) {
    int subtree = 1;

    tour[timer] = u;
    tin[u] = timer++;
    depth[u] = depth[p] + 1;

    for (const auto &v : adj[u]) {
        if (v != p) 
            subtree += dfs(v, u);
    }

    if (subtree == 1) {
        pq.push(u);
        valid[u] = 1;

        st.insert(tin[u]);
    }

    tout[u] = timer - 1;

    return subtree;
}

bool is_anc(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }

int add_ball(int k) {
    int last = -1;

    while (k--) {
        // dbg(k, sz(pq));

        int v = pq.top();
        pq.pop();

        // dbg(v);

        if (!valid[v]) continue;
        valid[v] = 0;
        present[v] = 1;

        st.insert(tin[v]);

        for (const auto &node : adj[v]) {
            if (node == par[v]) continue;
            st.erase(tin[node]);
        }

        last = v;

        if (par[v] != 0) {
            bool can_add = true;

            for (const auto &x : adj[par[v]]) {
                if (x == par[par[v]]) continue;
                if (!present[x]) can_add = false;
            }

            if (can_add) {
                pq.emplace(par[v]);
                valid[par[v]] = 1;
            }
        }            
    }

    return last;
}

int remove_ball(int v) {
    auto ancestor = st.upper_bound(tin[v]);
    ancestor--;

    int u = tour[*ancestor];
    valid[u] = true;
    present[u] = false;
    pq.emplace(u);

    st.erase(ancestor);

    for (const auto &x : adj[u]) {
        if (x == par[u]) continue;

        st.insert(tin[x]);
        break;
    }

    return depth[v] - depth[u];
}   

void solve() {
    int N, Q;
    cin >> N >> Q;

    for (int i = 1; i <= N; i++) {
        cin >> par[i];

        if (par[i] == 0) {
            root = i;
            continue;
        }

        adj[i].push_back(par[i]);
        adj[par[i]].push_back(i);
    }

    dfs(root, 0);

    while (Q--) {
        int type, x;
        cin >> type >> x;

        if (type == 1) cout << add_ball(x) << "\n";
        else cout << remove_ball(x) << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 5356 KB Execution killed with signal 6
2 Runtime error 97 ms 16616 KB Execution killed with signal 6
3 Incorrect 71 ms 8552 KB Output isn't correct
4 Runtime error 6 ms 5356 KB Execution killed with signal 6
5 Runtime error 7 ms 5356 KB Execution killed with signal 6
6 Runtime error 9 ms 5612 KB Execution killed with signal 6
7 Runtime error 7 ms 5484 KB Execution killed with signal 6
8 Runtime error 7 ms 5484 KB Execution killed with signal 6
9 Runtime error 9 ms 6124 KB Execution killed with signal 11
10 Runtime error 21 ms 8300 KB Execution killed with signal 6
11 Runtime error 82 ms 17260 KB Execution killed with signal 6
12 Incorrect 72 ms 9448 KB Output isn't correct
13 Incorrect 130 ms 9704 KB Output isn't correct

Subtask #2
8.57142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 5996 KB Output is correct
2 Runtime error 172 ms 28648 KB Execution killed with signal 6
3 Correct 89 ms 12648 KB Output is correct
4 Runtime error 31 ms 12012 KB Execution killed with signal 6
5 Runtime error 36 ms 12396 KB Execution killed with signal 6
6 Runtime error 62 ms 13164 KB Execution killed with signal 6
7 Runtime error 27 ms 10988 KB Execution killed with signal 6
8 Correct 43 ms 5996 KB Output is correct
9 Runtime error 77 ms 26988 KB Execution killed with signal 6
10 Runtime error 147 ms 28648 KB Execution killed with signal 6
11 Incorrect 166 ms 15080 KB Output isn't correct
12 Runtime error 111 ms 24808 KB Execution killed with signal 6
13 Incorrect 91 ms 14444 KB Output isn't correct
14 Correct 95 ms 12648 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 54 ms 16492 KB Execution killed with signal 11
2 Runtime error 134 ms 24936 KB Execution killed with signal 6
3 Correct 84 ms 14448 KB Output is correct
4 Runtime error 90 ms 22636 KB Execution killed with signal 6
5 Runtime error 99 ms 23788 KB Execution killed with signal 6
6 Runtime error 120 ms 23916 KB Execution killed with signal 6
7 Runtime error 98 ms 21228 KB Execution killed with signal 6
8 Correct 82 ms 14064 KB Output is correct
9 Runtime error 125 ms 27244 KB Execution killed with signal 6
10 Runtime error 128 ms 28136 KB Execution killed with signal 11
11 Runtime error 131 ms 28136 KB Execution killed with signal 11
12 Runtime error 131 ms 25064 KB Execution killed with signal 6
13 Correct 141 ms 16996 KB Output is correct
14 Execution timed out 1090 ms 12576 KB Time limit exceeded

Subtask #4
0.555555555556 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 121 ms 27244 KB Execution killed with signal 6
2 Runtime error 132 ms 25064 KB Execution killed with signal 6
3 Incorrect 94 ms 15848 KB Output isn't correct
4 Runtime error 113 ms 27116 KB Execution killed with signal 6
5 Runtime error 123 ms 28584 KB Execution killed with signal 6
6 Incorrect 147 ms 15208 KB Output isn't correct
7 Runtime error 123 ms 25128 KB Execution killed with signal 6
8 Incorrect 96 ms 15852 KB Output isn't correct
9 Correct 94 ms 12900 KB Output is correct