Submission #787313

#	Time	Username	Problem	Language	Result	Execution time	Memory
787313		SteGG	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	574 ms	45928 KiB

ballmachine

//Judges with GCC >= 12 only needs Ofast
//#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
//MLE optimization
//#pragma GCC optimize("conserve-stack")
//Old judges
//#pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
//New judges. Test with assert(__builtin_cpu_supports("avx2"));
//#pragma GCC target("arch=skylake")
//Atcoder
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//write variables and debug
#define bugf cout << "Here" << endl
#define bug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define bugarr(arr,...) cout << #arr; _dbg_arr(arr, __VA_ARGS__)

template<class T, class U>
ostream& operator<<(ostream& output, const pair<T, U> &A){
	output << "(" << A.first << ", " << A.second <<  ")";
	return output;
}

template <class T>
ostream& operator<<(ostream& output, const vector<T> &arr){
	int n = arr.size();
	output << "[";
	for(int i = 0; i < n; i++){
		output << arr[i];
		if(i != n - 1) output << ", ";
	}
	output << "]";
	return output;
}

template<class T>
ostream& operator<<(ostream& output, const set<T> &s){
	output << "{";
	for(auto it = s.begin(); it != s.end(); it++){
		if(it != s.begin()) output << ", ";
		output << (*it);
	}
	output << "}";
	return output;
}

template<class T, class U>
ostream& operator<<(ostream& output, const map<T, U> &m){
	output << "{";
	for(auto it = m.begin(); it != m.end(); it++){
		if(it != m.begin()) output << ", ";
		output << "(" << it->first << " : " << it->second << ")";
	}
	output << "}";
	return output;
}

template<class TH>
void _dbg(const char *sdbg, TH h){
	cout << sdbg << " = " << h << endl;
}

template<class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
	while(*sdbg != ',')cout << *sdbg++;
	cout << " = " << h << "\n";
	_dbg(sdbg+1, a...);
}

template<class _Arr, class _Index>
void _dbg_arr(_Arr arr, _Index index){
	cout << '[' << index << "] = " << arr[index] << endl;
}

template<class _Arr, class _Index, class... TA>
void _dbg_arr(_Arr &arr, _Index index, TA... args){
	cout << '[' << index << ']';
	_dbg_arr(arr[index], args...);
}

//open file
#define taskname "" //name input and output file

#ifdef SteGG
void open(){
	if(fopen("input.inp", "r")){
		freopen("input.inp", "r", stdin);
		freopen("output.out", "w", stdout);
	}
}
#else
void open(){
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
		freopen(taskname".out", "w", stdout);
	}
}
#endif

//initialize
#define testcase \
	long long test; \
	cin >> test; \
	for(int tst = 1; tst <= test; tst++)
#define int long long
#define MOD 1000000007
#define FFTMOD (119 << 23 | 1)
#define EPSILON 1e-9
#define setpre(x) fixed << setprecision(x)
#define cd complex<double>
#define all(x) x.begin(), x.end()

const long long INF = 3e18L + 5;
const int inf = 1e9 + 7;
const double infd = 1e60;
const double PI = acos(-1);
const int maxn = 1e5 + 5;
const int base = 32;
int n, q;
int root;
vector<int> tr[maxn];
int up[base][maxn];
int d[maxn];
int min_vertex[maxn];
int topo_sort[maxn];
int sz_topo;
int get_topo_sort_index[maxn];

//others struct or class

struct Segtree{
	vector<int> st;
	vector<bool> lazy;

	Segtree(int _len){
		st.assign(_len * 4, 0);
		lazy.assign(_len * 4, false);
	}

	void fix(int l, int r, int id){
		if(!lazy[id - 1]) return;
		st[id - 1] = r - l + 1;
		if(l != r){
			lazy[2*id - 1] = true;
			lazy[2*id] = true;
		}

		lazy[id - 1] = false;
	}

	int update(int l, int r, int id, int k){
		fix(l, r, id);
		
		assert(k);

		if(l == r){
			st[id - 1] = 1;
			return l;
		}

		int mid = (l + r) >> 1;
		fix(l, mid, 2*id);

		int return_pos;
		if(st[2*id - 1] < mid - l + 1){
			int diff = mid - l + 1 - st[2*id - 1];
			if(diff >= k){
				return_pos = update(l, mid, 2*id, k);
			}else{
				lazy[2*id - 1] = true;
				return_pos = update(mid + 1, r, 2*id + 1, k - diff);
			}
		}else{
			return_pos = update(mid + 1, r, 2*id + 1, k);
		}

		fix(l, mid, 2*id);
		fix(mid + 1, r, 2*id + 1);
		st[id - 1] = st[2*id - 1] + st[2*id];

		return return_pos;
	}

	void turnoff(int l, int r, int id, int p){
		fix(l, r, id);
		if(l == r){
			st[id - 1] = 0;
			return;
		}

		int mid = (l + r) >> 1;

		if(p <= mid){
			turnoff(l, mid, 2*id, p);
		}else{
			turnoff(mid + 1, r, 2*id + 1, p);
		}

		fix(l, mid, 2*id);
		fix(mid + 1, r, 2*id + 1);
		st[id - 1] = st[2*id - 1] + st[2*id];
	}


	int get(int l, int r, int id, int p){
		fix(l, r, id);
		if(l == r) return st[id - 1];

		int mid = (l + r) >> 1;
		if(p <= mid){
			return get(l, mid, 2*id, p);
		}else{
			return get(mid + 1, r, 2*id + 1, p);
		}
	}
};

//others function

//others init

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	open();
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		int p;
		cin >> p;
		if(p == 0) root = i;
		else{
			tr[p].push_back(i);
		}
	}

	auto dfs = [&](auto &&dfs, int u, int p) -> void {
		min_vertex[u] = u;
		for(int v : tr[u]){
			if(v == p) continue;
			d[v] = d[u] + 1;
			up[0][v] = u;
			for(int i = 1; i < base; i++){
				up[i][v] = up[i - 1][up[i - 1][v]];
			}
			dfs(dfs, v, u);
			min_vertex[u] = min(min_vertex[u], min_vertex[v]);
		}

		sort(all(tr[u]), [](int u, int v){
			return min_vertex[u] < min_vertex[v];
		});
	};

	dfs(dfs, root, 0);

	auto get_topo_sort = [&](auto &&get_topo_sort, int u, int p) -> void {
		for(int v : tr[u]){
			if(v == p) continue;
			get_topo_sort(get_topo_sort, v, u);
		}
		topo_sort[++sz_topo] = u;
		get_topo_sort_index[u] = sz_topo;
	};

	sz_topo = 0;
	get_topo_sort(get_topo_sort, root, 0);

	// for(int i = 1; i <= n; i++){
	// 	cout << topo_sort[i] << " \n"[i == n];
	// }

	Segtree st(n);

	while(q--){
		int type, a;
		cin >> type >> a;
		if(type == 1){
			cout << topo_sort[st.update(1, n, 1, a)] << endl;
		}else{
			int highest = a;

			for(int i = base - 1; i >= 0; i--){
				if(up[i][highest] == 0 || !st.get(1, n, 1, get_topo_sort_index[up[i][highest]])) continue;
				highest = up[i][highest];
			}

			st.turnoff(1, n, 1, get_topo_sort_index[highest]);

			cout << d[a] - d[highest] << endl;
		}
	}

	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void open()':
ballmachine.cpp:101:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:102:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   freopen(taskname".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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