Submission #411024

#	Time	Username	Problem	Language	Result	Execution time	Memory
411024		LptN21	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	249 ms	24272 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 P[N][M], fen[N];
vector<int> adj[N];
int pos[N], idx[N];
int _dp[N], cnt=0;

bool cmp(const int &a, const int &b) {return _dp[a]<_dp[b];}
void dfs(int u) {
    _dp[u]=u;
    for(int v, i=0;i<sz(adj[u]);i++) {
        v=adj[u][i], P[v][0]=u;
        dfs(v), _dp[u]=min(_dp[u], _dp[v]);
    }
    sort(adj[u].begin(), adj[u].end(), cmp);
}
void dfs2(int u) {
    for(int i=0;i<sz(adj[u]);i++) dfs2(adj[u][i]);
    pos[u]=++cnt, idx[cnt]=u;
}

void process(int s) {
    dfs(s), dfs2(s);
    for(int j=1;j<M;j++) for(int i=1;i<=n;i++)
        P[i][j]=P[P[i][j-1]][j-1];
}
void upd(int i, int v) {for(;i<=n;i+=i&-i) fen[i]+=v;}
int get(int i) {int res=0;for(;i>0;i-=i&-i) res+=fen[i];return res;}

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);
    process(0), memset(fen, 0, sizeof(int)*(cnt+1));
    for(int ans=0, i=1;i<=m;ans=0, i++) {
        scanf("%d%d", &t, &k);
        if(t&1) {
            for(int j=1;j<=k;j++) {
                int l=1, mid, r=n;ans=n;
                while(l<=r) {
                    mid=(l+r)/2;
                    if(get(mid)==mid) l=mid+1;
                    else ans=mid, r=mid-1;
                }
                upd(ans, 1), ans=idx[ans];
            }
        } else {
            for(int tmp, i=M-1;i>=0;i--) {
                tmp=get(pos[P[k][i]])-get(pos[P[k][i]]-1);
                if(tmp==1) k=P[k][i], ans+=(1<<i);
            }
            upd(pos[k], -1);
        }
        printf("%d\n", ans);
    }
    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:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d%d", &n, &m);int u;
      |     ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:51:43: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     for(int i=1;i<=n;adj[u].pb(i++)) scanf("%d", &u);
      |                                      ~~~~~^~~~~~~~~~
ballmachine.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d%d", &t, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~

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