Submission #623438

#	Time	Username	Problem	Language	Result	Execution time	Memory
623438		tamthegod	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	723 ms	63300 KiB

ballmachine

#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, q;
vector<int> adj[maxN];
int root;
int dp[maxN];
int order[maxN];
int mark[maxN];
int f[maxN][21];
int depth[maxN];
void ReadInput()
{
    cin >> n >> q;
    for(int i=1; i<=n; i++)
    {
        int p;
        cin >> p;
        if(!p)
        {
            root = i;
            continue;
        }
        adj[p].pb(i);
        adj[i].pb(p);
    }
}
void predfs(int u, int par)
{
    dp[u] = u;
    for(int v : adj[u])
    {
        if(v == par) continue;
        depth[v] = depth[u] + 1;
        f[v][0] = u;
        for(int i=1; i<=18; i++)
            f[v][i] = f[f[v][i - 1]][i - 1];
        predfs(v, u);
        dp[u] = min(dp[u], dp[v]);
    }
}
int t = 0;
void dfs(int u, int par)
{
    vector<pair<int, int>> vc;
    for(int v : adj[u])
    {
        if(v == par) continue;
        vc.pb({dp[v], v});
    }
    sort(vc.begin(), vc.end());
    for(pair<int, int> v : vc)
        dfs(v.se, u);
    order[u] = ++t;
    //cout << u << " ";
}
struct cmp
{
    bool operator ()(int i, int j) const
    {
        return order[i] < order[j];
    };
};
void Solve()
{
    predfs(root, 0);
    dfs(root, 0);
    int p = 0;
    set<int, cmp> s;
   // for(int i=1; i<=n; i++) cout << order[i] << " ";return;
    for(int i=1; i<=n; i++) s.insert(i);
    while(q--)
    {
        int type;
        cin >> type;
        if(type == 1)
        {
            int k;
            cin >> k;
            while(k--)
            {
                if(!k) cout << *s.begin() << '\n';
                s.erase(s.begin());
            }
        }
        else
        {
            int u;
            cin >> u;
            int tmp = depth[u];
            for(int i=18; i>=0; i--)
            {
                int t = f[u][i];
                if(t && s.find(t) == s.end()) u = t;
            }
         //   cout << u;return;
            cout << tmp - depth[u] << '\n';
            s.insert(u);
        }
    }
}
int32_t main()
{
  //  freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Compilation message (stderr)

ballmachine.cpp: In function 'void Solve()':
ballmachine.cpp:79:9: warning: unused variable 'p' [-Wunused-variable]
   79 |     int p = 0;
      |         ^

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