제출 #1159856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159856		yhkhoo	Specijacija (COCI20_specijacija)	C++20	0 / 110	15 ms	39808 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
typedef pair<int, pii> pip;
#define pb push_back
#define eb emplace_back
typedef long long ll;

const int MAXN = 1001, MAXV = (MAXN+1)*(MAXN+2)/2, LMV = 19;

int n, v, q, t;
int a[MAXN], kp[MAXV][LMV], d[MAXV];

int main(){
	cin.tie(0); ios_base::sync_with_stdio(0);
	cin >> n >> q >> t;
	v = (n+1)*(n+2)/2;
	d[1] = 0;
	for(int i=0; i<n+1; i++){
		if(i != n) cin >> a[i];
		int s = (i)*(i+1)/2+1;
		int ns = s+i+1;
		int cn = ns;
		/*cerr << i << ':' << s << ' ' << ns << '\n';/**/
		for(int j=s; j<ns; j++){
			kp[cn][0] = j;
			d[cn] = i+1;
			if(a[i] == j){
				cn++;
				kp[cn][0] = j;
				d[cn] = i+1;
			}
			cn++;
		}
	}
	/*for(int i=1; i<=v; i++){
		cerr << i << ':' << kp[i][0] << '\n';
	}/**/
	for(int k=1; k<LMV; k++){
		for(int i=1; i<=v; i++){
			kp[i][k] = kp[kp[i][k-1]][k-1];
		}
	}
	while(q--){
		int x, y;
		cin >> x >> y;
		if(x > y) swap(x, y);
		for(int k = LMV-1; k >= 0; k--){
			if(d[kp[y][k]] >= d[x]){
				y = kp[y][k];
			}
		}
		if(x == y){
			cout << x << '\n';
			continue;
		}
		for(int k = LMV-1; k >= 0; k--){
			if(kp[x][k] != kp[y][k]){
				x = kp[x][k];
				y = kp[y][k];
			}
		}
		cout << kp[x][0] << '\n';
	}
}

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