oj.uz

Submission #959399

# Submission time Handle Problem Language Result Execution time Memory
959399 2024-04-08T07:01:19 Z Yang8on Ball Machine (BOI13_ballmachine) C++14
7.53968 / 100
 1000 ms 26964 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];
}

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

        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 solve()':
ballmachine.cpp:170:30: warning: left operand of comma operator has no effect [-Wunused-value]
  170 |             for(int j = 1; j <= n, u; j ++)
      |                            ~~^~~~
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 4 ms 7004 KB Output isn't correct
2 Incorrect 40 ms 15376 KB Output isn't correct
3 Incorrect 903 ms 14032 KB Output isn't correct
4 Incorrect 1 ms 6876 KB Output isn't correct
5 Incorrect 2 ms 7004 KB Output isn't correct
6 Incorrect 2 ms 7004 KB Output isn't correct
7 Incorrect 2 ms 7004 KB Output isn't correct
8 Incorrect 2 ms 7004 KB Output isn't correct
9 Incorrect 4 ms 7260 KB Output isn't correct
10 Incorrect 9 ms 8796 KB Output isn't correct
11 Incorrect 51 ms 13588 KB Output isn't correct
12 Incorrect 852 ms 13600 KB Output isn't correct
13 Incorrect 46 ms 13488 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 11096 KB Output is correct
2 Execution timed out 1073 ms 21772 KB Time limit exceeded
3 Incorrect 788 ms 17348 KB Output isn't correct
4 Incorrect 24 ms 10576 KB Output isn't correct
5 Incorrect 148 ms 10400 KB Output isn't correct
6 Incorrect 140 ms 11812 KB Output isn't correct
7 Incorrect 63 ms 11092 KB Output isn't correct
8 Correct 19 ms 9564 KB Output is correct
9 Incorrect 98 ms 22480 KB Output isn't correct
10 Execution timed out 1100 ms 21744 KB Time limit exceeded
11 Incorrect 93 ms 22132 KB Output isn't correct
12 Incorrect 360 ms 20040 KB Output isn't correct
13 Correct 61 ms 24660 KB Output is correct
14 Incorrect 849 ms 17244 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1034 ms 15692 KB Time limit exceeded
2 Execution timed out 1056 ms 19784 KB Time limit exceeded
3 Execution timed out 1054 ms 22604 KB Time limit exceeded
4 Execution timed out 1028 ms 19264 KB Time limit exceeded
5 Execution timed out 1039 ms 18736 KB Time limit exceeded
6 Execution timed out 1062 ms 18484 KB Time limit exceeded
7 Execution timed out 1047 ms 16988 KB Time limit exceeded
8 Execution timed out 1066 ms 22528 KB Time limit exceeded
9 Execution timed out 1054 ms 22208 KB Time limit exceeded
10 Execution timed out 1033 ms 21612 KB Time limit exceeded
11 Execution timed out 1054 ms 21548 KB Time limit exceeded
12 Execution timed out 1022 ms 19600 KB Time limit exceeded
13 Execution timed out 1053 ms 26452 KB Time limit exceeded
14 Incorrect 52 ms 17616 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 22048 KB Time limit exceeded
2 Execution timed out 1049 ms 19504 KB Time limit exceeded
3 Correct 68 ms 26964 KB Output is correct
4 Execution timed out 1046 ms 21888 KB Time limit exceeded
5 Execution timed out 1024 ms 22100 KB Time limit exceeded
6 Incorrect 168 ms 22100 KB Output isn't correct
7 Execution timed out 1040 ms 19536 KB Time limit exceeded
8 Correct 107 ms 26880 KB Output is correct
9 Incorrect 298 ms 16964 KB Output isn't correct