oj.uz

Submission #959411

# Submission time Handle Problem Language Result Execution time Memory
959411 2024-04-08T07:15:43 Z Yang8on Ball Machine (BOI13_ballmachine) C++14
100 / 100
 515 ms 25516 KB 
#include <bits/stdc++.h>
#define Y8o "Ball Machine"
#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];
}

int dd[maxn];

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);

    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]; });

    dfs2(root);

    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';

//        if(id == 1)
//        {
//            int pos = -1;
//            for(int j = 1; j <= n, u; j ++)
//            {
//                if(dd[j]) continue;
//                dd[j] = 1, pos = a[j], u --;
//            }
//            cout << pos << '\n';
//        }
//        else
//        {
//            int dem = 0;
//            while(dd[ pos[cha[u][0]] ]) u = cha[u][0], dem ++;
//            cout << dem << '\n', dd[pos[u]] = 0;
//        }
    }
}


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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 149 ms 11228 KB Output is correct
3 Correct 134 ms 10968 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 3 ms 3164 KB Output is correct
9 Correct 10 ms 3704 KB Output is correct
10 Correct 28 ms 4956 KB Output is correct
11 Correct 161 ms 11192 KB Output is correct
12 Correct 122 ms 10832 KB Output is correct
13 Correct 137 ms 10836 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 7344 KB Output is correct
2 Correct 383 ms 19292 KB Output is correct
3 Correct 143 ms 14960 KB Output is correct
4 Correct 171 ms 8688 KB Output is correct
5 Correct 218 ms 8016 KB Output is correct
6 Correct 213 ms 7956 KB Output is correct
7 Correct 212 ms 7200 KB Output is correct
8 Correct 127 ms 7372 KB Output is correct
9 Correct 312 ms 19804 KB Output is correct
10 Correct 384 ms 19492 KB Output is correct
11 Correct 318 ms 19664 KB Output is correct
12 Correct 391 ms 17444 KB Output is correct
13 Correct 240 ms 22484 KB Output is correct
14 Correct 159 ms 15076 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 11640 KB Output is correct
2 Correct 445 ms 18288 KB Output is correct
3 Correct 297 ms 21216 KB Output is correct
4 Correct 227 ms 17384 KB Output is correct
5 Correct 284 ms 17000 KB Output is correct
6 Correct 312 ms 16928 KB Output is correct
7 Correct 284 ms 15452 KB Output is correct
8 Correct 303 ms 21348 KB Output is correct
9 Correct 367 ms 20696 KB Output is correct
10 Correct 464 ms 20296 KB Output is correct
11 Correct 466 ms 20284 KB Output is correct
12 Correct 435 ms 18140 KB Output is correct
13 Correct 515 ms 25516 KB Output is correct
14 Correct 148 ms 15052 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 20624 KB Output is correct
2 Correct 433 ms 18256 KB Output is correct
3 Correct 234 ms 24604 KB Output is correct
4 Correct 442 ms 20480 KB Output is correct
5 Correct 426 ms 20052 KB Output is correct
6 Correct 372 ms 19748 KB Output is correct
7 Correct 486 ms 18124 KB Output is correct
8 Correct 244 ms 24656 KB Output is correct
9 Correct 136 ms 14804 KB Output is correct