Submission #445543

#	Time	Username	Problem	Language	Result	Execution time	Memory
445543		grt	Specijacija (COCI20_specijacija)	C++17	0 / 110	418 ms	408628 KiB

Main

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 4000000 + 10;
int n, q, t;
int seq[nax];

vi V[nax];

int par[nax][19], dp[nax];

void dfs(int x) {
	for(int nbh : V[x]) {
		dp[nbh] = dp[x] + 1;
		dfs(nbh);
		par[nbh][0] = x;
	}
}

int lca(int a, int b) {
	if(dp[a] < dp[b]) swap(a, b);
	for(int i = 18; i >= 0; --i) {
		if(dp[par[a][i]] >= dp[b]) {
			a = par[a][i];
		}
	}
	if(a == b) return a;
	for(int i = 18; i >= 0; --i) {
		if(par[a][i] != par[b][i]) {
			a = par[a][i];
			b = par[b][i];
		}
	}
	return par[a][0];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q >> t;
	int start = 1;
	for(int i = 1; i <= n; ++i) {
		cin >> seq[i];
		for(int j = start; j < start + i; ++j) {
			assert(j < nax);
			if(j <= seq[i]) V[j].PB(j + i);
			if(j >= seq[i]) V[j].PB(j + i + 1);
		}
		start += i;
	}
	start += n + 1;
	dp[1] = 1;
	dfs(1);
	for(int s = 1; s <= 18; ++s) {
		for(int i = 1; i <= start; ++i) {
			par[i][s] = par[par[i][s - 1]][s - 1];
		}
	}
	while(q--) {
		ll x, y;
		cin >> x >> y;
		cout << lca(x, y) << "\n";
	}
}

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