oj.uz

Submission #959389

# Submission time Handle Problem Language Result Execution time Memory
959389 2024-04-08T06:41:08 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 639 ms 27264 KB 
#include <bits/stdc++.h>
#define Y8o "ballmachine"
#define maxn 100005
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)

using namespace std;

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);
}
void iof() {
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
        freopen(Y8o".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}


int n, Q, root, cnt;
int Min[maxn], cha[maxn][18], h[maxn], pos[maxn], a[maxn];
vector<int> o[maxn];

void dfs(int u)
{
    for(int v : o[u])
    {
        h[v] = h[u] + 1, cha[v][0] = u;
        for(int j = 1; j <= 17; j ++) cha[v][j] = cha[cha[v][j - 1]][j - 1];
        dfs(v);
        Min[u] = min({ Min[u], Min[v] });
    }
    Min[u] = min(Min[u], u);
}
void dfs2(int u)
{
    for(int v : o[u]) dfs2(v);
    a[++ cnt] = u;
    pos[u] = cnt;
}

struct dl { int val, lazy; } st[4 * maxn];

void build(int id = 1, int l = 1, int r = n)
{
    if(l == r)
    {
        st[id] = {0, -1};
        return;
    }
    int mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);

    st[id].val = st[id * 2].val + st[id * 2 + 1].val;
    st[id].lazy = -1;
}
void down(int id, int l, int r)
{
    int t = st[id].lazy;
    if(t == -1) return ;

    int mid = (l + r) >> 1;

    st[id * 2] = {t * (mid - l + 1), t};
    st[id * 2 + 1] = {t * (r - mid), t};

    st[id].lazy = -1;
}
void update(int u, int v, int val, int id = 1, int l = 1, int r = n)
{
    if(v < l || r < u) return ;
    if(u <= l && r <= v)
    {
        st[id] = {val * (r - l + 1), val};
        return ;
    }

    down(id, l, r);
    int mid = (l + r) >> 1;

    update(u, v, val, id * 2, l, mid);
    update(u, v, val, id * 2 + 1, mid + 1, r);

    st[id].val = st[id * 2].val + st[id * 2 + 1].val;
}
int get(int u, int v, int id = 1, int l = 1, int r = n)
{
    if(v < l || r < u) return 0;
    if(u <= l && r <= v) return st[id].val;

    down(id, l, r);
    int mid = (l + r) >> 1;

    return get(u, v, id * 2, l, mid) + get(u, v, id * 2 + 1, mid + 1, r);
}
int add(int x)
{
    int l = 1, r = n;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(get(1, mid) + x <= mid) r = mid - 1;
        else l = mid + 1;
    }

    update(1, l, 1);
    return a[l];
}
int jump(int u, int len)
{
    for(int i = 0; i <= 17; i ++) if(gb(len, i)) u = cha[u][i];
    return u;
}
int erase_(int u)
{
    int l = 1, r = n;
    while(l <= r)
    {
        int mid = (l + r) >> 1, v = jump(u, mid);
        if(v != 0 && get(pos[v], pos[v]) == 1) l = mid + 1;
        else r = mid - 1;
    }

    int par = jump(u, r);
    update(pos[par], pos[par], 0);

    return h[u] - h[par];
}

void solve()
{
    cin >> n >> Q;
    for(int i = 1, v; i <= n; i ++)
    {
        cin >> v;
        if(v == 0) root = i;
        else o[v].push_back(i);
    }

    memset(Min, 0x3f, sizeof Min);

    dfs(root);
    dfs2(root);

    for(int i = 1; i <= n; i ++) if(o[i].size())
        sort(o[i].begin(), o[i].end(), [](int x, int y) { return Min[x] < Min[y]; });

    build();

    for(int i = 1, id, u; i <= Q; i ++)
    {
        cin >> id >> u;
        if(id == 1) cout << add(u) << '\n';
        else cout << erase_(u) << '\n';
    }
}


int main()
{
    iof();

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

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

    ctime();
    return 0;
}

Compilation message

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

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7000 KB Output isn't correct
2 Incorrect 157 ms 15556 KB Output isn't correct
3 Incorrect 132 ms 15576 KB Output isn't correct
4 Incorrect 2 ms 7000 KB Output isn't correct
5 Incorrect 3 ms 7004 KB Output isn't correct
6 Incorrect 4 ms 7004 KB Output isn't correct
7 Incorrect 2 ms 7004 KB Output isn't correct
8 Incorrect 3 ms 7004 KB Output isn't correct
9 Incorrect 10 ms 7004 KB Output isn't correct
10 Incorrect 33 ms 9812 KB Output isn't correct
11 Incorrect 151 ms 15360 KB Output isn't correct
12 Incorrect 137 ms 15696 KB Output isn't correct
13 Incorrect 142 ms 15508 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 12176 KB Output is correct
2 Incorrect 377 ms 21736 KB Output isn't correct
3 Incorrect 193 ms 17252 KB Output isn't correct
4 Incorrect 241 ms 8972 KB Output isn't correct
5 Incorrect 237 ms 8912 KB Output isn't correct
6 Incorrect 220 ms 13648 KB Output isn't correct
7 Incorrect 209 ms 13144 KB Output isn't correct
8 Correct 131 ms 11860 KB Output is correct
9 Incorrect 344 ms 22328 KB Output isn't correct
10 Incorrect 483 ms 22080 KB Output isn't correct
11 Incorrect 389 ms 21904 KB Output isn't correct
12 Incorrect 417 ms 19796 KB Output isn't correct
13 Correct 310 ms 24616 KB Output is correct
14 Incorrect 179 ms 17204 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 14784 KB Output isn't correct
2 Incorrect 541 ms 20136 KB Output isn't correct
3 Correct 325 ms 23252 KB Output is correct
4 Incorrect 267 ms 19436 KB Output isn't correct
5 Incorrect 282 ms 18980 KB Output isn't correct
6 Incorrect 321 ms 19172 KB Output isn't correct
7 Incorrect 284 ms 17628 KB Output isn't correct
8 Correct 334 ms 23420 KB Output is correct
9 Incorrect 373 ms 22392 KB Output isn't correct
10 Incorrect 611 ms 21992 KB Output isn't correct
11 Incorrect 494 ms 22284 KB Output isn't correct
12 Incorrect 488 ms 20044 KB Output isn't correct
13 Correct 639 ms 27168 KB Output is correct
14 Incorrect 144 ms 17256 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 467 ms 22476 KB Output isn't correct
2 Incorrect 457 ms 20016 KB Output isn't correct
3 Correct 275 ms 26916 KB Output is correct
4 Incorrect 409 ms 22440 KB Output isn't correct
5 Incorrect 464 ms 22068 KB Output isn't correct
6 Incorrect 407 ms 21860 KB Output isn't correct
7 Incorrect 445 ms 19916 KB Output isn't correct
8 Correct 247 ms 27264 KB Output is correct
9 Incorrect 153 ms 17100 KB Output isn't correct