oj.uz

Submission #787313

# Submission time Handle Problem Language Result Execution time Memory
787313 2023-07-19T04:56:09 Z SteGG Ball Machine (BOI13_ballmachine) C++17
100 / 100
 574 ms 45928 KB 
//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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2936 KB Output is correct
2 Correct 286 ms 24932 KB Output is correct
3 Correct 195 ms 25064 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2936 KB Output is correct
6 Correct 4 ms 3196 KB Output is correct
7 Correct 3 ms 3196 KB Output is correct
8 Correct 4 ms 3156 KB Output is correct
9 Correct 16 ms 4208 KB Output is correct
10 Correct 40 ms 8396 KB Output is correct
11 Correct 273 ms 24860 KB Output is correct
12 Correct 179 ms 25056 KB Output is correct
13 Correct 245 ms 24884 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 11044 KB Output is correct
2 Correct 541 ms 40584 KB Output is correct
3 Correct 187 ms 36008 KB Output is correct
4 Correct 205 ms 14548 KB Output is correct
5 Correct 279 ms 14416 KB Output is correct
6 Correct 247 ms 14528 KB Output is correct
7 Correct 239 ms 13040 KB Output is correct
8 Correct 124 ms 11124 KB Output is correct
9 Correct 481 ms 41024 KB Output is correct
10 Correct 542 ms 40592 KB Output is correct
11 Correct 425 ms 40556 KB Output is correct
12 Correct 541 ms 37972 KB Output is correct
13 Correct 277 ms 40872 KB Output is correct
14 Correct 188 ms 36048 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 22168 KB Output is correct
2 Correct 561 ms 38728 KB Output is correct
3 Correct 310 ms 37196 KB Output is correct
4 Correct 274 ms 33452 KB Output is correct
5 Correct 337 ms 33172 KB Output is correct
6 Correct 332 ms 33136 KB Output is correct
7 Correct 351 ms 31596 KB Output is correct
8 Correct 312 ms 37184 KB Output is correct
9 Correct 425 ms 41100 KB Output is correct
10 Correct 566 ms 40792 KB Output is correct
11 Correct 574 ms 40800 KB Output is correct
12 Correct 562 ms 38696 KB Output is correct
13 Correct 536 ms 45928 KB Output is correct
14 Correct 286 ms 36176 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 41212 KB Output is correct
2 Correct 522 ms 38700 KB Output is correct
3 Correct 274 ms 45868 KB Output is correct
4 Correct 469 ms 41216 KB Output is correct
5 Correct 570 ms 40684 KB Output is correct
6 Correct 466 ms 40692 KB Output is correct
7 Correct 512 ms 38816 KB Output is correct
8 Correct 273 ms 45748 KB Output is correct
9 Correct 192 ms 36092 KB Output is correct