oj.uz

Submission #959465

# Submission time Handle Problem Language Result Execution time Memory
959465 2024-04-08T09:00:29 Z Neco_arc Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 63 ms 17608 KB 
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "Ball Machine"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n, q, N, rt;
int Min[maxn], h[maxn], a[maxn];
vector<int> edges[maxn];

void pre_dfs(int u, int par) {
    for(int v : edges[u]) if(v != par) {
        Min[u] = min(Min[u], Min[v]);
        pre_dfs(v, u);
    }
}

void dfs(int u, int par) {
    for(int v : edges[u]) if(v != par) h[v] = h[u] + 1, dfs(v, u);
    a[++N] = u;
}

void solve()
{

    cin >> n >> q;

    int rt = 0;
    fi(i, 1, n) {
        int x; cin >> x;
        if(x == 0) rt = i;
        else edges[x].push_back(i);
    }

    pre_dfs(rt, 0);
    fi(i, 1, n) sort(all(edges[i]), [](int x, int y) { return Min[x] < Min[y]; } );
    dfs(rt, 0);

    N = 0;

    fi(i, 1, q) {
        int type, x;
        cin >> type >> x;

        if(type == 1) N += x, cout << a[N] << '\n';
        else cout << h[x] - h[a[N]] << '\n', --N;

    }

}


int main()
{

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

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

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

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4956 KB Output isn't correct
2 Incorrect 29 ms 8292 KB Output isn't correct
3 Incorrect 26 ms 8096 KB Output isn't correct
4 Incorrect 3 ms 4952 KB Output isn't correct
5 Incorrect 2 ms 4956 KB Output isn't correct
6 Incorrect 2 ms 4956 KB Output isn't correct
7 Incorrect 3 ms 5212 KB Output isn't correct
8 Incorrect 3 ms 5212 KB Output isn't correct
9 Incorrect 4 ms 5212 KB Output isn't correct
10 Incorrect 8 ms 5724 KB Output isn't correct
11 Incorrect 34 ms 8284 KB Output isn't correct
12 Incorrect 29 ms 8056 KB Output isn't correct
13 Incorrect 28 ms 8304 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7772 KB Output is correct
2 Incorrect 47 ms 13308 KB Output isn't correct
3 Incorrect 29 ms 8928 KB Output isn't correct
4 Incorrect 22 ms 8288 KB Output isn't correct
5 Incorrect 21 ms 8028 KB Output isn't correct
6 Incorrect 22 ms 8028 KB Output isn't correct
7 Incorrect 21 ms 7524 KB Output isn't correct
8 Correct 18 ms 7772 KB Output is correct
9 Incorrect 47 ms 13604 KB Output isn't correct
10 Incorrect 42 ms 13136 KB Output isn't correct
11 Incorrect 39 ms 13148 KB Output isn't correct
12 Incorrect 38 ms 11604 KB Output isn't correct
13 Correct 40 ms 15952 KB Output is correct
14 Incorrect 31 ms 8912 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 9308 KB Output isn't correct
2 Incorrect 39 ms 11612 KB Output isn't correct
3 Correct 44 ms 14736 KB Output is correct
4 Incorrect 38 ms 11644 KB Output isn't correct
5 Incorrect 30 ms 11360 KB Output isn't correct
6 Incorrect 28 ms 11556 KB Output isn't correct
7 Incorrect 27 ms 10192 KB Output isn't correct
8 Correct 32 ms 14684 KB Output is correct
9 Incorrect 41 ms 13648 KB Output isn't correct
10 Incorrect 41 ms 13140 KB Output isn't correct
11 Incorrect 45 ms 13140 KB Output isn't correct
12 Incorrect 40 ms 11604 KB Output isn't correct
13 Correct 42 ms 17608 KB Output is correct
14 Incorrect 33 ms 9372 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 13736 KB Output isn't correct
2 Incorrect 39 ms 11736 KB Output isn't correct
3 Correct 42 ms 17232 KB Output is correct
4 Incorrect 43 ms 13648 KB Output isn't correct
5 Incorrect 42 ms 13140 KB Output isn't correct
6 Incorrect 46 ms 13364 KB Output isn't correct
7 Incorrect 40 ms 11536 KB Output isn't correct
8 Correct 63 ms 17240 KB Output is correct
9 Incorrect 34 ms 8992 KB Output isn't correct