Submission #484533

#	Time	Username	Problem	Language	Result	Execution time	Memory
484533		idas	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	587 ms	32840 KiB

ballmachine

#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define F first
#define S second
#define PB push_back
#define MP make_pair

using namespace std;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pff;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;

const int INF=1e9, MOD=1e9+7;

void setIO()
{
    FAST_IO;
}

void setIO(string s)
{
    FAST_IO;
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int N=1e5+10, L=28;
int n, q, p[N][L], mn[N], dp[N];
vi ad[N];

void mini(int u, int pst)
{
    mn[u]=u;
    for(auto x : ad[u]){
        if(x==pst) continue;
        mini(x, u);
        mn[u]=min(mn[u], mn[x]);
    }
}

void bdp(int u, int pst)
{
    for(auto x : ad[u]){
        if(x==pst) continue;
        dp[x]=dp[u]+1;
        bdp(x, u);
    }
}

void ord(int u)
{
    vector<pii> inf;
    for(auto x : ad[u]){
        inf.PB({mn[x], x});
    }
    sort(inf.begin(), inf.end());
    ad[u].clear();
    for(auto[x, y] : inf){
        ad[u].PB(y);
    }
}

int in;
mii c;
priority_queue<pii, vector<pii>, greater<pii>> pq;
bool is[N];

void dfs(int u, int pst)
{
    for(auto x : ad[u]){
        if(x==pst) continue;
        dfs(x, u);
    }
    c[u]=++in;
    pq.push({in, u});
}

void build()
{
    FOR(i, 1, L)
    {
        FOR(j, 0, n)
        {
            p[j][i]=p[p[j][i-1]][i-1];
        }
    }
}

int lift(int x, int d)
{
    FOR(i, 0, L) if(d&(1<<i)) x=p[x][i];
    return x;
}

int fnd(int x)
{
    int l=0, r=dp[x];
    while(l<r){
        int m=(l+r+1)/2;
        if(!is[lift(x, m)]) r=m-1;
        else l=m;
    }
    return l;
}

int main()
{
    setIO();
    cin >> n >> q;
    int rt;
    FOR(i, 0, n)
    {
        int x; cin >> x; x--;
        x==-1?x=i,rt=i:x=x;
        p[i][0]=x;
        if(x!=i){
            ad[x].PB(i);
            ad[i].PB(x);
        }
    }
    build();
    mini(rt, -1);
    FOR(i, 0, n) ord(i);
    dfs(rt, -1);
    bdp(rt, -1);
    while(q--){
        int t; cin >> t;
        if(t==1){
            int k; cin >> k;
            FOR(i, 0, k-1)
            {
                int u=pq.top().S; pq.pop();
                is[u]=true;
            }
            int u=pq.top().S; pq.pop();
            is[u]=true;
            cout << u+1 << '\n';
        }
        else{
            int x; cin >> x; x--;
            int l=fnd(x), u=lift(x, l);
            cout << l << '\n';
            is[u]=false;
            pq.push({c[u], u});
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'void setIO(std::string)':
ballmachine.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:131:8: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  131 |     bdp(rt, -1);
      |     ~~~^~~~~~~~

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