oj.uz

답안 #385938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
385938 2021-04-05T09:08:06 Z arujbansal Ball Machine (BOI13_ballmachine) C++17
17.6984 / 100
 1000 ms 28264 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--) {
        assert(!pq.empty());
        int v = pq.top();
        pq.pop();

        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 9 ms 5376 KB Execution killed with signal 6
2 Runtime error 104 ms 17512 KB Execution killed with signal 6
3 Incorrect 76 ms 9448 KB Output isn't correct
4 Runtime error 6 ms 5356 KB Execution killed with signal 6
5 Runtime error 8 ms 5356 KB Execution killed with signal 6
6 Runtime error 7 ms 5484 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 90 ms 16620 KB Execution killed with signal 6
12 Incorrect 76 ms 8680 KB Output isn't correct
13 Incorrect 127 ms 8832 KB Output isn't correct

Subtask #2
8.57142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 5484 KB Output is correct
2 Runtime error 155 ms 27752 KB Execution killed with signal 6
3 Correct 85 ms 11880 KB Output is correct
4 Runtime error 32 ms 11884 KB Execution killed with signal 6
5 Runtime error 38 ms 12268 KB Execution killed with signal 6
6 Runtime error 62 ms 12496 KB Execution killed with signal 6
7 Runtime error 27 ms 10732 KB Execution killed with signal 6
8 Correct 42 ms 5484 KB Output is correct
9 Runtime error 77 ms 26476 KB Execution killed with signal 6
10 Runtime error 156 ms 28264 KB Execution killed with signal 6
11 Incorrect 165 ms 14696 KB Output isn't correct
12 Runtime error 114 ms 24296 KB Execution killed with signal 6
13 Incorrect 77 ms 13804 KB Output isn't correct
14 Correct 102 ms 12008 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 54 ms 16128 KB Execution killed with signal 11
2 Runtime error 139 ms 24680 KB Execution killed with signal 6
3 Correct 90 ms 13424 KB Output is correct
4 Runtime error 85 ms 22252 KB Execution killed with signal 6
5 Runtime error 99 ms 23532 KB Execution killed with signal 6
6 Runtime error 99 ms 23532 KB Execution killed with signal 6
7 Runtime error 90 ms 20716 KB Execution killed with signal 6
8 Correct 93 ms 13424 KB Output is correct
9 Runtime error 131 ms 26516 KB Execution killed with signal 6
10 Runtime error 133 ms 27700 KB Execution killed with signal 11
11 Runtime error 148 ms 27624 KB Execution killed with signal 11
12 Runtime error 131 ms 24552 KB Execution killed with signal 6
13 Correct 147 ms 16484 KB Output is correct
14 Execution timed out 1093 ms 12008 KB Time limit exceeded

Subtask #4
0.555555555556 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 126 ms 26476 KB Execution killed with signal 6
2 Runtime error 126 ms 24684 KB Execution killed with signal 6
3 Incorrect 94 ms 15208 KB Output isn't correct
4 Runtime error 112 ms 26476 KB Execution killed with signal 6
5 Runtime error 126 ms 27980 KB Execution killed with signal 6
6 Incorrect 183 ms 14952 KB Output isn't correct
7 Runtime error 128 ms 24680 KB Execution killed with signal 6
8 Incorrect 91 ms 15484 KB Output isn't correct
9 Correct 95 ms 12388 KB Output is correct