Submission #1159779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159779		YSH2020	Specijacija (COCI20_specijacija)	C++20	10 / 110	4094 ms	1864 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
int depth(int x) {
	if ((int)(pow(8*x+1, 0.5)+1)/2 == (pow(8*x+1, 0.5)+1)/2) return (pow(8*x+1, 0.5)+1)/2-1;
	else return (int)(pow(8*x+1, 0.5)+1)/2;
}
signed main() {
	int n; cin >> n;
	int q; cin >> q;
	int t; cin >> t;
	int a[n+1];
	for (int i = 1; i < n+1; i++) {
		int x; cin >> x;
		a[i] = x-((i-1)*i)/2;
	}
	while (q--) {
		int x, y; cin >> x >> y;
		//first check for depth
		if (y > x) swap(x, y);
		while (depth(x) != depth(y)) {
			//set x to its parent
			int tmp = depth(x);
			if (x-((tmp-1)*tmp)/2 > a[tmp-1]) x--;
			x -= (tmp-1);
		}
		while (x != y) {
			//set it to its parent
			int tmp = depth(x);
			if (x-((tmp-1)*tmp)/2 > a[tmp-1]) x--;
			x -= (tmp-1);
			if (y-((tmp-1)*tmp)/2 > a[tmp-1]) y--;
			y -= (tmp-1);
		}
		cout << x << '\n';
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60