oj.uz

답안 #959410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
959410 2024-04-08T07:15:08 Z Yang8on Ball Machine (BOI13_ballmachine) C++14
60.0794 / 100
 1000 ms 25940 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 solve()':
ballmachine.cpp:171:30: warning: left operand of comma operator has no effect [-Wunused-value]
  171 |             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
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 41 ms 12116 KB Output is correct
3 Correct 38 ms 11860 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 3 ms 3164 KB Output is correct
7 Correct 2 ms 3160 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 4 ms 3676 KB Output is correct
10 Correct 9 ms 5376 KB Output is correct
11 Correct 38 ms 12124 KB Output is correct
12 Correct 37 ms 11872 KB Output is correct
13 Correct 39 ms 11856 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 8028 KB Output is correct
2 Correct 80 ms 21072 KB Output is correct
3 Correct 43 ms 15816 KB Output is correct
4 Correct 24 ms 9048 KB Output is correct
5 Correct 24 ms 8796 KB Output is correct
6 Correct 25 ms 8872 KB Output is correct
7 Correct 26 ms 8028 KB Output is correct
8 Correct 19 ms 8020 KB Output is correct
9 Correct 85 ms 21716 KB Output is correct
10 Correct 77 ms 20932 KB Output is correct
11 Correct 65 ms 20832 KB Output is correct
12 Correct 64 ms 18768 KB Output is correct
13 Correct 61 ms 23636 KB Output is correct
14 Correct 44 ms 15824 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1038 ms 12372 KB Time limit exceeded
2 Execution timed out 1069 ms 18772 KB Time limit exceeded
3 Execution timed out 1053 ms 21608 KB Time limit exceeded
4 Execution timed out 1056 ms 17488 KB Time limit exceeded
5 Execution timed out 1025 ms 17556 KB Time limit exceeded
6 Execution timed out 1063 ms 17636 KB Time limit exceeded
7 Execution timed out 1047 ms 16096 KB Time limit exceeded
8 Execution timed out 1012 ms 21452 KB Time limit exceeded
9 Execution timed out 1044 ms 21136 KB Time limit exceeded
10 Execution timed out 1060 ms 20472 KB Time limit exceeded
11 Execution timed out 1047 ms 20280 KB Time limit exceeded
12 Execution timed out 1060 ms 18516 KB Time limit exceeded
13 Execution timed out 1044 ms 25684 KB Time limit exceeded
14 Correct 72 ms 16716 KB Output is correct

Subtask #4
2.22222222222 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1065 ms 20732 KB Time limit exceeded
2 Execution timed out 1047 ms 18648 KB Time limit exceeded
3 Correct 68 ms 25936 KB Output is correct
4 Execution timed out 1046 ms 20836 KB Time limit exceeded
5 Execution timed out 1025 ms 20236 KB Time limit exceeded
6 Correct 162 ms 20924 KB Output is correct
7 Execution timed out 1030 ms 18652 KB Time limit exceeded
8 Correct 68 ms 25940 KB Output is correct
9 Correct 45 ms 15824 KB Output is correct