Submission #493470

#	Time	Username	Problem	Language	Result	Execution time	Memory
493470		goodluck2020	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	136 ms	23792 KiB

ballmachine

#include <bits/stdc++.h>
#define task "ballmachine"
#define sz(X) ((int)X.size())

using namespace std;
const int N = 1e5 + 5;
int n, q, Root, Min[N], Rank[N], Time, P[N][20], HasBall[N];
vector < int > V[N];
struct Data
{
    int id, rk;
};
struct cmp
{
    bool operator() (Data A, Data B)
    {
        return A.rk > B.rk;
    }
};
priority_queue < Data , vector < Data > , cmp > NoBall;
void dfs1(int u)
{
    Min[u] = u;
    for(int v : V[u])
    {
        dfs1(v);
        Min[u] = min(Min[u], Min[v]);
    }
    sort(V[u].begin(), V[u].end(),
         [](int x, int y)
         {
             return Min[x] < Min[y];
         });
}
void dfs2(int u)
{
    for(int i = 0; i < sz(V[u]); i++)
    {
        int v = V[u][i];
        dfs2(v);
    }
    Rank[u] = ++Time;
}
void Build()
{
    dfs1(Root);
    dfs2(Root);
    for(int i = 1; i < 20; i++)
        for(int j = 1; j <= n; j++)
        P[j][i] = P[P[j][i-1]][i-1];
    for(int i = 1; i <= n; i++) NoBall.push({i, Rank[i]});
}
int Solve1(int k)
{
    int res;
    while(k)
    {
        k--;
        res = NoBall.top().id;
        HasBall[res] = 1;
        NoBall.pop();
    }
    return res;
}
int Solve2(int k)
{
    int res = 0;
    for(int i = 19; i >= 0; i--)
        if(HasBall[P[k][i]]) k = P[k][i], res += 1 << i;
    HasBall[k] = 0;
    NoBall.push({k, Rank[k]});
    return res;
}
int main()
{
    if(fopen(task ".inp","r"))
    {
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        int p;
        cin >> p;
        if(p == 0) Root = i;
        P[i][0] = p;
        V[p].push_back(i);
    }
    Build();
    while(q--)
    {
        int type, k;
        cin >> type >> k;
        if(type == 1) cout << Solve1(k) << '\n';
        else cout << Solve2(k) << '\n';
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int Solve1(int)':
ballmachine.cpp:63:12: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |     return res;
      |            ^~~

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