Submission #410725

#	Time	Username	Problem	Language	Result	Execution time	Memory
410725		LptN21	Ball Machine (BOI13_ballmachine)	C++14	32.70 / 100	1100 ms	22208 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define FF first
#define SS second
#define pb push_back
#define sz(x) (int)x.size()
#define oo 1e9
#define PI acos(-1.0)
#define lb lower_bound
#define ub upper_bound
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
const int N = 1e5+7, M=18;
const int MOD = 1e9+7;

int n, m, k, t;
int h[N], P[N][M];
vector<int> adj[N];
int vsz[N], sum[N];
int _dp[N];

bool cmp(const int &a, const int &b) {return _dp[a]<_dp[b];}
void dfs(int u) {
    vsz[u]=1, _dp[u]=u;
    for(int v, i=0;i<sz(adj[u]);i++) {
        v=adj[u][i], h[v]=h[u]+1, P[v][0]=u;
        dfs(v), vsz[u]+=vsz[v];
        _dp[u]=min(_dp[u], _dp[v]);
    }
}
void dfs2(int u) {
    for(int v, i=0;i<sz(adj[u]);i++) {
        v=adj[u][i];
        if(sum[v]==vsz[v]) continue;
        sum[u]-=sum[v], dfs2(v), sum[u]+=sum[v];
        if(!k) break;
    }
    if(k) {
        k--, sum[u]++;
        if(!k) printf("%d\n", u);
    }
}

void process(int s) {
    memset(P, -1, sizeof P), h[s]=-1, dfs(s);
    memset(sum, 0, sizeof sum);
    for(int j=0;(1<<j)<=n;j++)
        for(int i=1;i<=n;i++)
            if(P[i][j-1]!=-1)
                P[i][j]=P[P[i][j-1]][j-1];
}
int kth(int u, int k) {
    if(h[u]<k) return 0;
    int log=log2(h[u]);
    for(int i=log;i>=0;i--)
        if(k>=(1<<i)) u=P[u][i], k-=(1<<i);
    return u;
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    //fastIO;
    scanf("%d%d", &n, &m);int u;
    for(int i=1;i<=n;adj[u].pb(i++)) scanf("%d", &u);
    vsz[0]=-1, sum[0]=oo, process(0);
    for(int i=0;i<=n;i++) sort(adj[i].begin(), adj[i].end(), cmp);
    for(int i=1;i<=m;i++) {
        scanf("%d%d", &t, &k);
        if(t&1) dfs2(0);
        else {
            int l=0, r=h[k], mid, ans=h[k];
            while(l<=r) {
                mid=(l+r)/2, t=kth(k, mid);
                if(vsz[t]==sum[t]) l=mid+1, ans=mid;
                else r=mid-1;
            }
            printf("%d\n", ans);t=kth(k, ans);
            while(t>0) sum[t]--, t=P[t][0];
        }
    }
    return 0;
}
/* stuff you should look for
    - int overflow, array bounds
    - special cases (n=1?)
    - do smth instead of do nothing and stay organized
    - WRITE STUFF DOWN
    - DONT JUST STICK ON ONE APPROACH
*/

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d%d", &n, &m);int u;
      |     ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:67:43: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     for(int i=1;i<=n;adj[u].pb(i++)) scanf("%d", &u);
      |                                      ~~~~~^~~~~~~~~~
ballmachine.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d%d", &t, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~

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