Submission #1159833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159833		justin271828	Specijacija (COCI20_specijacija)	C++17	0 / 110	135 ms	100740 KiB

Main

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

#define l2 long long

l2 p[543210][20];
l2 d[543210];

int main() {
	l2 n, que, t;
	cin >> n >> que >> t;
	l2 com = ((n+1)*(n+2))/2;
	l2 a[n];
	set<l2> as;
	for (l2 i = 0; i < n; i++) {
		cin >> a[i];
		as.insert(a[i]);}
	memset(p, -1, sizeof(p));
	d[1] = 0;
	queue<l2> q;
	q.push(1);
	q.push(1);
	l2 counter = 1;
	while (!q.empty()) {
		if (counter >= com) break;
		p[++counter][0] = q.front();
		d[counter] = d[q.front()]+1;
		q.pop();
		q.push(counter);
		if (as.find(counter) != as.end()) q.push(counter);}
	for (l2 k = 1; k < 20; k++) {
		for (l2 i = 0; i < 543210; i++) {
			if (p[i][k-1] == -1) p[i][k] = -1;
			else p[i][k] = p[p[i][k-1]][k-1];}}
	l2 z = 0;
	for (l2 qwerty = 0; qwerty < que; qwerty++) {
		l2 x, y;
		cin >> x >> y;
		x += z*t;
		y += z*t;
		x--;
		y--;
		x %= com;
		y %= com;
		x++;
		y++;
		if (d[x] < d[y]) swap(x, y);
		for (l2 k = 19; k >= 0; k--) {
			if (d[x]-d[y] >= 1<<k) x = p[x][k];}
		for (l2 k = 19; k >= 0; k--) {
			if (p[x][k] != p[y][k]) {
				x = p[x][k];
				y = p[y][k];}}
		if (x != y) x = p[x][0];
		z = x;
		cout << z << "\n";}
	return 0;}

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