Submission #882546

#	Time	Username	Problem	Language	Result	Execution time	Memory
882546		arashMLG	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	95 ms	64704 KiB

ballmachine

#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

typedef long long     ll;
typedef pair<int,int> pii;

const int N = 5e5 + 23;
const int LOG = 20;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

int n,q;
int val[N],ft[N];
int timer;
priority_queue<pii, vector<pii> , greater<> > pq;
vector<int> G[N];
int up[LOG][N];
bool is[N];

void dfs1(int v) {
	val[v] = v;
	for(int u : G[v]) {
		dfs1(u);
		val[v] = min(val[v],val[u]);
	}
}

void dfs2(int v) {
	sort(all(G[v]) , [&] (int x,int y) { return val[x] < val[y];});
	for(int u : G[v]) {
		dfs2(u);
	}
	ft[v] = timer ++;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>q;
	int root=-1;
	for(int i = 1; i <= n; i ++) {
		int p; cin>>p;
		up[0][i] = p;
		if(p == 0) root = i;
		else G[p].pb(i);
	}
	for(int i = 1; i< LOG; i++) 
		for(int v= 1; v <= n ; v ++)
			up[i][v] = up[i-1][up[i-1][v]];
	dfs1(root);
	dfs2(root);
	for(int i = 1; i<= n ; i ++) {
		pq.push({ ft[i],i});
	}
	while(q--) {
		int k,x; cin>>k>>x;
		if(k == 1) {
			debug("BEGIN",1);
			int ans=-1;
			debug(x);
			while(x--) {
				int v = pq.top().S; pq.pop();
				debug(v);
				is[v] = true;
				ans = v;
			}	
			cout<<ans << '\n'; debug("END",1);	
		} else {
			debug("BEGIN",2);
			int ans=0;
			debug(x);
			for(int i = LOG-1; i >= 0 ; i--) {
				if(is[up[i][x]])
					ans += (1 << i), x = up[i][x];
			}
			debug(x);
			is[x] = false;
			pq.push({ft[x],x});
			cout<<ans << '\n';  debug("END",2);
		}
	}
	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:70:4: note: in expansion of macro 'debug'
   70 |    debug("BEGIN",1);
      |    ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:72:4: note: in expansion of macro 'debug'
   72 |    debug(x);
      |    ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:75:5: note: in expansion of macro 'debug'
   75 |     debug(v);
      |     ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:79:23: note: in expansion of macro 'debug'
   79 |    cout<<ans << '\n'; debug("END",1);
      |                       ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:81:4: note: in expansion of macro 'debug'
   81 |    debug("BEGIN",2);
      |    ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:83:4: note: in expansion of macro 'debug'
   83 |    debug(x);
      |    ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:88:4: note: in expansion of macro 'debug'
   88 |    debug(x);
      |    ^~~~~
ballmachine.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
ballmachine.cpp:91:24: note: in expansion of macro 'debug'
   91 |    cout<<ans << '\n';  debug("END",2);
      |                        ^~~~~

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