Submission #386183

#	Time	Username	Problem	Language	Result	Execution time	Memory
386183		ak2006	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	353 ms	34796 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n = 1e5 + 5,root = -1,q;
int timer = 0;
vvi adj(n),dp(n,vi(21));
vi out(n),minNode(n),dep(n);
vb is(n);
set<pair<int,int>>unfilled;
bool cmp(int u,int v)
{
    return minNode[u] < minNode[v];
}
int compute(int u,int p)
{
    minNode[u] = u;
    for (int v:adj[u])if (v != p)minNode[u] = min(minNode[u],compute(v,u));
    return minNode[u];
}
void dfs(int u,int p)
{
    dep[u] = dep[p] + 1;
    dp[u][0] = p;
    for (int i = 1;i<=20;i++)dp[u][i] = dp[dp[u][i - 1]][i - 1];
    sort(adj[u].begin(),adj[u].end(),cmp);
    for (int v:adj[u]){
        if (v == p)continue;
        dfs(v,u);
    }
    out[u] = ++timer;
    unfilled.insert({out[u],u});
}
int add()
{
    auto it = unfilled.begin();
    unfilled.erase(it);
    is[(*it).second] = 1;
    return (*it).second;
}
int sub(int u)
{
    int v = u;
    for (int i = 20;i>=0;i--){
        if (is[dp[v][i]])v = dp[v][i];
    }
    is[v] = 0;
    unfilled.insert({out[v],v});
    return dep[u] - dep[v];
}
int main()
{
    fast;
    cin>>n>>q;
    for (int i = 0;i<n;i++){
        int p;
        cin>>p;
        p--;
        if (p == -1)root = i;
        else adj[p].pb(i);
    }
    compute(root,root);
    dfs(root,root);
    while (q--){
        int t,u;
        cin>>t>>u;
        if (t == 1){
            while (u-- > 1)add();
            cout<<add() + 1<<'\n';
        }
        else{
            cout<<sub(u - 1)<<'\n';
        }
    }
    return 0;
}

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