Submission #647701

#	Time	Username	Problem	Language	Result	Execution time	Memory
647701		PoonYaPat	Ball Machine (BOI13_ballmachine)	C++14	24.80 / 100	246 ms	29996 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,m,p[100001][18],mmin[100001],root,dis[100001],pos[100001];
vector<int> adj[100001],ord;

int dfs(int x, int par) {
    mmin[x]=x;
    dis[x]=dis[par]+1;
    for (auto s : adj[x]) {
        if (s==par) continue;
        mmin[x]=min(mmin[x],dfs(s,x));
    }
    return mmin[x];
}

void dfs_ord(int x, int par) {
    vector<pii> v;
    for (auto s : adj[x]) {
        if (s==par) continue;
        v.push_back(pii(mmin[s],s));
    }
    sort(v.begin(),v.end());
    for (auto s : v) dfs_ord(s.second,x);
    ord.push_back(x);
}

void dfs_par(int x, int par) {
    for (int i=1; i<=17; ++i) p[x][i]=p[p[x][i-1]][i-1];
    for (auto s : adj[x]) {
        if (s==par) continue;
        dfs_par(s,x);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=1; i<=n; ++i) {
        int x; cin>>x;
        p[i][0]=x;
        adj[x].push_back(i);
        if (x==0) root=x;
    }

    dfs(root,root);
    dfs_ord(root,root);
    dfs_par(root,root);

    for (int i=0; i<n; ++i) pos[ord[i]]=i;
    pos[0]=100010;

    int cnt=-1;
    while (m--) {
        int mode,x; cin>>mode>>x;
        if (mode==1) {
            cnt+=x;
            cout<<ord[cnt]<<"\n";
        } else {
            int y=x;
            for (int i=20; i>=0; --i) if (pos[p[x][i]]<=cnt) x=p[x][i];
            cout<<dis[y]-dis[x]<<"\n";
            --cnt;
        }
    }
}

• Subtask 1: 3.8461538461538463 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 8.571428571428571 / 40
• Subtask 4: 1.6666666666666667 / 5