Submission #43593

#	Time	Username	Problem	Language	Result	Execution time	Memory
43593		PowerOfNinjaGo	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	270 ms	68572 KiB

ballmachine

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vii vector< pair<int, int> >
typedef long long ll;
using namespace std;
vi adj[100005];
vi post;
int dp[22][100005];
int ft[100005];
int n;
int markdown[100005];
int pos[100005];
int minn[100005];
bool cmp(int a, int b)
{
    return minn[a]< minn[b];
}
void dfs(int u)
{
    minn[u] = u;
    for(auto v: adj[u])
    {
        dfs(v);
        minn[u] = min(minn[u], minn[v]);
    }
    sort(adj[u].begin(), adj[u].end(), cmp);
}
void dfs2(int u)
{
    for(auto v: adj[u]) dfs2(v);
    pos[u] = post.size();
    post.pb(u);
}
void add(int id, int dx)
{
    for(; id<= n; id += id&(-id)) ft[id] += dx;
}
int sum(int idx)
{
    int res = 0;
    for(; idx; idx -= idx&(-idx)) res += ft[idx];
    return res;
}
int findVacant()
{
    int lo = 1, hi = n;
    while(lo< hi)
    {
        int mid = (lo+hi)/2;
        if(sum(mid) > 0) hi = mid;
        else lo = mid+1;
    }
    add(lo, -1);
    markdown[post[lo]] = 1;
    return lo;
}
int findTop(int x)
{
    int cur = 20;
    int levs = 0;
    for(; cur>= 0; cur--)
    {
        int poss = dp[cur][x];
        if(poss == 0) continue;
        if(markdown[poss] == 1)
        {
            levs += (1<<cur);
            x = poss;
        }
    }
    add(pos[x], 1);
    markdown[x] = 0;
    return levs;
}
int main()
{
    int q;
    scanf("%d %d", &n, &q);
    int root = 0;
    post.pb(-1);
    for(int i = 1; i<= n; i++)
    {
        int p; scanf("%d", &p);
        adj[p].pb(i);
        dp[0][i] = p;
        if(p == 0) root = i;
        add(i, 1);
    }
    for(int i = 1; i<= 20; i++)
    {
        for(int j = 1; j<= n; j++)
        {
            dp[i][j] = dp[i-1][dp[i-1][j]];
        }
    }
    dfs(root);
    dfs2(root);
    while(q--)
    {
        int c, x; scanf("%d %d", &c, &x);
        if(c == 1)
        {
            int res = 0;
            while(x--) res = findVacant();
            printf("%d\n", post[res]);
        }
        else
        {
            printf("%d\n", findTop(x));
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:83:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
                           ^
ballmachine.cpp:88:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int p; scanf("%d", &p);
                               ^
ballmachine.cpp:105:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int c, x; scanf("%d %d", &c, &x);
                                         ^

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