oj.uz

Submission #959412

# Submission time Handle Problem Language Result Execution time Memory
959412 2024-04-08T07:16:31 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 605 ms 25976 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 147 ms 11576 KB Output is correct
3 Correct 120 ms 11576 KB Output is correct
4 Correct 2 ms 3160 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 3 ms 3164 KB Output is correct
8 Correct 4 ms 3164 KB Output is correct
9 Correct 10 ms 3676 KB Output is correct
10 Correct 31 ms 5596 KB Output is correct
11 Correct 151 ms 11424 KB Output is correct
12 Correct 136 ms 11760 KB Output is correct
13 Correct 137 ms 11496 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 7864 KB Output is correct
2 Correct 400 ms 20444 KB Output is correct
3 Correct 163 ms 15936 KB Output is correct
4 Correct 147 ms 8688 KB Output is correct
5 Correct 223 ms 8612 KB Output is correct
6 Correct 210 ms 8796 KB Output is correct
7 Correct 194 ms 7676 KB Output is correct
8 Correct 128 ms 7928 KB Output is correct
9 Correct 307 ms 20956 KB Output is correct
10 Correct 357 ms 20304 KB Output is correct
11 Correct 329 ms 20736 KB Output is correct
12 Correct 391 ms 18256 KB Output is correct
13 Correct 289 ms 23312 KB Output is correct
14 Correct 185 ms 15784 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 12196 KB Output is correct
2 Correct 524 ms 18680 KB Output is correct
3 Correct 333 ms 22184 KB Output is correct
4 Correct 251 ms 17872 KB Output is correct
5 Correct 292 ms 17508 KB Output is correct
6 Correct 350 ms 17312 KB Output is correct
7 Correct 261 ms 15700 KB Output is correct
8 Correct 359 ms 21924 KB Output is correct
9 Correct 361 ms 21092 KB Output is correct
10 Correct 553 ms 20676 KB Output is correct
11 Correct 558 ms 20684 KB Output is correct
12 Correct 420 ms 18568 KB Output is correct
13 Correct 605 ms 25976 KB Output is correct
14 Correct 134 ms 15992 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 21220 KB Output is correct
2 Correct 443 ms 19164 KB Output is correct
3 Correct 239 ms 25424 KB Output is correct
4 Correct 465 ms 21424 KB Output is correct
5 Correct 449 ms 20688 KB Output is correct
6 Correct 387 ms 20648 KB Output is correct
7 Correct 505 ms 18532 KB Output is correct
8 Correct 259 ms 25424 KB Output is correct
9 Correct 138 ms 15708 KB Output is correct