oj.uz

답안 #881309

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881309 2023-12-01T05:14:18 Z noompty Ball Machine (BOI13_ballmachine) C++17
48.9072 / 100
 104 ms 30804 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <array>
#include <random>
#include <string>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
 
#define ll long long
#define f first
#define s second
 
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
 
template<typename A> void __print(const A &x);
template<typename A, typename B> void __print(const pair<A, B> &p);
template<typename... A> void __print(const tuple<A...> &t);
template<typename T> void __print(stack<T> s);
template<typename T> void __print(queue<T> q);
template<typename T, typename... U> void __print(priority_queue<T, U...> q);
 
template<typename A> void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}
 
template<typename A, typename B> void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.f);
    cerr << ',';
    __print(p.s);
    cerr << ')';
}
 
template<typename... A> void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first] (const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}
 
template<typename T> void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}
 
template<typename T> void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
template<typename T, typename... U> void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
void _print() { cerr << "]\n"; }
 
template <typename Head, typename... Tail> void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T)) cerr << ", ";
    _print(T...);
}
 
#ifdef DEBUG
	#define D(...) cerr << "Line: " << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
	#define D(...)
#endif

int n, q, rt, mn[100005], out[100005], idx, par[100005][20], k, v, ans, depth[100005], tmp;
bool filled[100005];
vector<int> adj[100005];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void dfs1(int curr) {
    mn[curr] = curr;
    for (int i : adj[curr]) {
        depth[i] = depth[curr] + 1;
        dfs1(i);
        mn[curr] = min(mn[curr], mn[i]);
    }
}

void dfs2(int curr) {
    vector<pair<int, int>> ord;
    for (int i : adj[curr]) {
        ord.push_back({mn[i], i});
    }
    sort(ord.begin(), ord.end());
    for (auto [m, x] : ord) {
        dfs2(x);
    }
    out[curr] = idx++;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> par[i][0];
        if (!par[i][0]) {
            rt = i;
            continue;
        }
        adj[par[i][0]].push_back(i);
    }

    dfs1(rt);
    dfs2(rt);

    for (int i = 1; i <= n; i++) {
        // cout << i << ": " << out[i] << " " << depth[i] << "\n";
        pq.push({out[i], i});
    }

    for (int i = 1; i < 20; i++) {
        for (int j = 1; j <= n; j++) {
            par[j][i] = par[par[j][i - 1]][i - 1];
        }
    }

    while (q--) {
        cin >> k >> v;
        if (k == 1) {
            while (v--) {
                ans = pq.top().s;
                filled[ans] = true;
                pq.pop();
            }
            cout << ans << "\n";
        } else {
            tmp = v;
            for (int i = 19; i >= 0; i--) {
                if (filled[par[tmp][i]]) {
                    tmp = par[tmp][i];
                }
            }
            cout << depth[v] - depth[tmp] << "\n";
            filled[tmp] = false;
            pq.push({mn[tmp], tmp});
        }
    }

}

Subtask #1
1.92307692308 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4700 KB Output isn't correct
2 Incorrect 60 ms 12308 KB Output isn't correct
3 Incorrect 39 ms 11988 KB Output isn't correct
4 Incorrect 1 ms 4700 KB Output isn't correct
5 Incorrect 1 ms 4700 KB Output isn't correct
6 Correct 1 ms 4696 KB Output is correct
7 Incorrect 2 ms 4696 KB Output isn't correct
8 Incorrect 2 ms 4700 KB Output isn't correct
9 Incorrect 5 ms 4980 KB Output isn't correct
10 Incorrect 13 ms 5468 KB Output isn't correct
11 Incorrect 59 ms 12236 KB Output isn't correct
12 Incorrect 38 ms 11988 KB Output isn't correct
13 Incorrect 56 ms 12164 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 8796 KB Output isn't correct
2 Incorrect 89 ms 23380 KB Output isn't correct
3 Correct 45 ms 15424 KB Output is correct
4 Incorrect 43 ms 10916 KB Output isn't correct
5 Incorrect 46 ms 10832 KB Output isn't correct
6 Incorrect 47 ms 10868 KB Output isn't correct
7 Incorrect 53 ms 9544 KB Output isn't correct
8 Incorrect 31 ms 8796 KB Output isn't correct
9 Correct 84 ms 23548 KB Output is correct
10 Incorrect 87 ms 23272 KB Output isn't correct
11 Incorrect 80 ms 23376 KB Output isn't correct
12 Incorrect 93 ms 19552 KB Output isn't correct
13 Incorrect 61 ms 28240 KB Output isn't correct
14 Correct 49 ms 15424 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 15116 KB Output is correct
2 Correct 82 ms 19792 KB Output is correct
3 Correct 77 ms 26528 KB Output is correct
4 Correct 76 ms 20832 KB Output is correct
5 Correct 56 ms 20560 KB Output is correct
6 Correct 63 ms 20560 KB Output is correct
7 Correct 53 ms 17500 KB Output is correct
8 Correct 66 ms 26412 KB Output is correct
9 Correct 94 ms 23636 KB Output is correct
10 Correct 88 ms 23292 KB Output is correct
11 Correct 101 ms 23464 KB Output is correct
12 Correct 104 ms 19792 KB Output is correct
13 Correct 96 ms 30800 KB Output is correct
14 Correct 68 ms 15556 KB Output is correct

Subtask #4
0.555555555556 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 93 ms 23888 KB Output isn't correct
2 Incorrect 99 ms 19788 KB Output isn't correct
3 Incorrect 66 ms 30804 KB Output isn't correct
4 Incorrect 98 ms 23864 KB Output isn't correct
5 Incorrect 85 ms 23380 KB Output isn't correct
6 Incorrect 79 ms 23512 KB Output isn't correct
7 Incorrect 84 ms 19716 KB Output isn't correct
8 Incorrect 64 ms 30800 KB Output isn't correct
9 Correct 46 ms 15432 KB Output is correct