Submission #78986

#	Time	Username	Problem	Language	Result	Execution time	Memory
78986		win11905	Ball Machine (BOI13_ballmachine)	C++11	0 / 100	155 ms	28348 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define x first
#define y second

const int N = 1e5+5;

int n, m;
int par[N][17], dep[N];
vector<int> g[N];
vector<pii> ng[N];

int dfs(int u) {
    int mn = u;
    for(int i = 1; i < 17; ++i) par[u][i] = par[par[u][i-1]][i-1];
    for(int v : g[u]) {
        dep[v] = dep[u] + 1, par[v][0] = u;
        int now = dfs(v); 
        mn = min(mn, now);
        ng[u].emplace_back(mn, v);
    }
    sort(ng[u].begin(), ng[u].end());
    return mn;
}

int A[N], ptr;
int pos[N];
int block = 320;
int sz[350];
bool d[N];
pii t[350];


void solve(int u) {
    for(auto v : ng[u]) solve(v.y);
    A[ptr++] = u;
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 1, val; i <= n; ++i) scanf("%d", &val), g[val].emplace_back(i);
    dep[1] = 1, dfs(1);
    solve(1);
    for(int i = 0; i < n; ++i) sz[i/block]++;
    int last = n / block;
    for(int i = 1; i <= n; ++i) pos[A[i]] = i;
    for(int i = 0, a, b; i < m; ++i) {
        scanf("%d %d", &a, &b);
        if(a == 1) {
            for(int i = 0; i <= last; ++i) {
                if(b - (sz[i] - t[i].x) > 0) b -= sz[i] - t[i].x, t[i] = pii(sz[i], 1);
                else {
                    assert(t[i].y == 0);
                    t[i] = pii(0, 0);
                    for(int j = i * block; j < i * block + sz[i]; ++j) {
                        if(d[j]) t[i].x++;
                        else if(b--) d[j] = true, t[i].x++;
                        if(!b) {
                            printf("%d\n", A[j]);
                            break;
                        }
                    }
                    break;
                } 
            } 
        } else {
            auto check = [&](int v) {
                if(t[pos[v]/block].y) return true;
                else if(d[pos[v]]) return true;
            };
            int sum = 0;
            for(int i = 16; ~i; --i) 
                if(check(par[b][i])) b = par[b][i], sum += 1<<i;
            printf("%d\n", sum);
            b = pos[b];
            int ith = b / block;
            if(t[ith].y) for(int j = ith * block; j < ith * block + sz[ith]; ++j) d[j] = 1;
            d[b] = 0;
            t[ith] = pii(0, 0);
            for(int j = ith * block; j < ith * block + sz[ith]; ++j) 
                t[ith].x += d[j]; 
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:43:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1, val; i <= n; ++i) scanf("%d", &val), g[val].emplace_back(i);
                                      ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp: In lambda function:
ballmachine.cpp:72:13: warning: control reaches end of non-void function [-Wreturn-type]
             };
             ^

• Subtask 1: 0 / 25
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40
• Subtask 4: 0 / 5