提出 48d4a46b-1c7b-496d-b12f-2463a66a5adc

コード

#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;

int main() {
	int n, q;
	cin >> n >> q;
	const int logk = 30;
	int input = 0;
	vector<vector<int>> doubling(logk, vector<int>(n, -1));
	vector<vector<int>> fill(logk * n);
	vector<int> dist(n, -1);
	long long ex = 1;
	int unknown = 0;
	rep(_, q) {
		int Case, x, y;
		cin >> Case >> x >> y;
		if (Case == 1) {
			x--;
			y--;
			if (doubling[0][x] == y) continue;
			input++;
			doubling[0][x] = y;
			queue<int> que;
			que.push(logk * x);
			while (!que.empty()) {
				int a = que.front() % logk;
				int b = que.front() / logk;
				que.pop();
				if (a != 0) doubling[a][b] = doubling[a - 1][doubling[a - 1][b]];
				if (doubling[a][b] == -1) {
					fill[logk * doubling[a - 1][b] + a - 1].push_back(logk * b + a);
					continue;
				}
				else if (a == logk - 1) continue;
				que.push(logk * b + a + 1);
				for (auto i : fill[logk * b + a]) {
					que.push(i);
				}
			}
			if (input == n - 1) {
				vector<vector<int>> rev(n);
				queue<int> next;
				rep(i, n) {
					if (doubling[0][i] == -1) unknown = i;
					else rev[doubling[0][i]].push_back(i);
				}
				next.push(unknown);
				dist[unknown] = 0;
				while (!next.empty()) {
					for (auto i : rev[next.front()]) {
						if (dist[i] > -1) {
							dist[i] = -1;
							goto FIN;
						}
						dist[i] = dist[next.front()] + 1;
						next.push(i);
					}
					next.pop();
				}
			FIN:
				int maxi = 0;
				for (auto i : dist) {
					if (i < 0) maxi = 200000;
					maxi = max(maxi, i);
				}
				rep(i, maxi + 1) {
					ex = lcm(ex, i + 1);
					if (ex > 1000000000) break;
				}
			}
		}
		else {
			x--;
			if (input == n - 1 && y > dist[x] && (y - dist[x]) % ex == 0) {
				cout << unknown + 1 << endl;
				continue;
			}
			int now = x;
			int cnt = 0;
			while (y > 0) {
				if (y % 2 == 1) now = doubling[cnt][now];
				if (now == -1) break;
				cnt++;
				y /= 2;
			}
			if (now == -1) now--;
			cout << now + 1 << endl;
		}
	}
	return 0;
}

結果

問題	点数	言語	結果	実行時間	メモリ
S. Association	100	C++ (gcc)	AC	1917 ms	48964 KiB

テストセット

テストセット	結果	得点	実行時間	メモリ
testcase1	AC × 20	20	15 ms	8448 KiB
testcase2	AC × 12	40	1443 ms	48708 KiB
testcase3	AC × 35	40	1917 ms	48964 KiB

詳細結果

テストケース	結果	実行時間	メモリ
sub1sub2sub3_hand_01.txt	AC	13 ms	8320 KiB
sub1sub2sub3_hand_02.txt	AC	13 ms	8320 KiB
sub1sub2sub3_hand_03.txt	AC	12 ms	8320 KiB
sub1sub2sub3_random_01.txt	AC	13 ms	8192 KiB
sub1sub2sub3_random_02.txt	AC	15 ms	8064 KiB
sub1sub2sub3_random_03.txt	AC	13 ms	8064 KiB
sub1sub3_corner_01.txt	AC	13 ms	8064 KiB
sub1sub3_corner_02.txt	AC	15 ms	8320 KiB
sub1sub3_corner_03.txt	AC	14 ms	8192 KiB
sub1sub3_corner_04.txt	AC	15 ms	7936 KiB
sub1sub3_corner_05.txt	AC	14 ms	8192 KiB
sub1sub3_corner_06.txt	AC	14 ms	8192 KiB
sub1sub3_corner_07.txt	AC	15 ms	8192 KiB
sub1sub3_example_01.txt	AC	15 ms	8192 KiB
sub1sub3_example_02.txt	AC	13 ms	8192 KiB
sub1sub3_hand_04.txt	AC	13 ms	8064 KiB
sub1sub3_hand_05.txt	AC	14 ms	8192 KiB
sub1sub3_random_04.txt	AC	14 ms	8448 KiB
sub1sub3_random_05.txt	AC	14 ms	8192 KiB
sub1sub3_random_06.txt	AC	14 ms	8320 KiB
sub2sub3_max_01.txt	AC	1310 ms	48708 KiB
sub2sub3_max_02.txt	AC	1401 ms	48708 KiB
sub2sub3_max_03.txt	AC	1443 ms	48708 KiB
sub2sub3_random_07.txt	AC	503 ms	40576 KiB
sub2sub3_random_08.txt	AC	1152 ms	25856 KiB
sub2sub3_random_09.txt	AC	679 ms	10112 KiB
sub3_corner_08.txt	AC	1890 ms	12032 KiB
sub3_corner_09.txt	AC	1778 ms	16640 KiB
sub3_corner_10.txt	AC	1917 ms	16384 KiB
sub3_max_04.txt	AC	1777 ms	48964 KiB
sub3_max_05.txt	AC	1713 ms	48832 KiB
sub3_max_06.txt	AC	1532 ms	48708 KiB
sub3_random_10.txt	AC	912 ms	22912 KiB
sub3_random_11.txt	AC	915 ms	27008 KiB
sub3_random_12.txt	AC	1268 ms	47688 KiB