Submission #79005

#	Time	Username	Problem	Language	Result	Execution time	Memory
79005		win11905	Ball Machine (BOI13_ballmachine)	C++11	16.23 / 100	1093 ms	32724 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];

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

set<int> S;

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 = 1; i <= n; ++i) pos[A[i]] = i;
    int ptr = 0;
    for(int i = 1; i <= n; ++i) S.emplace(i);
    for(int i = 0, a, b; i < m; ++i) {
        scanf("%d %d", &a, &b);
        if(a == 1) {
            while(b--) {
                if(!b) printf("%d\n", A[*S.begin()]);
                S.erase(S.begin());
            } 
        } else {
            int sum = 0;
            for(int i = 16; ~i; --i) 
                if(par[b][i] != 0 && S.count(pos[par[b][i]]) == 0) b = par[b][i], sum += 1<<i;
            S.emplace(pos[b]);
            printf("%d\n", sum);
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:44:9: warning: unused variable 'ptr' [-Wunused-variable]
     int ptr = 0;
         ^~~
ballmachine.cpp:39: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:40: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:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

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