公式解説

imoscon_s 解説

By
tyranno_gyaos

注意しておきたい事

この問題は，特殊なケースが存在する．
例えば，N=1N=1 のケースを考えれば明らかで，N=1N=1 のとき，Imosちゃんの連想ルールを考えると 11 といえば 11 しかありえない．したがって，以下のような入力例に対しては -1 ではなく 1 と出力すべきである．

1 1
2 1 100

ほかにも，今までに発言した Case1 の発言の種類が N−1N-1 個のとき，特殊に連想する数が確定するケースが複数存在する．詳しくは小課題4の解説に記述した．
また，この問題を解くうえでは連想配列など、アクセスに O(logN)O(logN) 掛かってしまう構造体を配列にして計算量を落とす工夫をした実装が要求される．十分に注意せよ．

小課題1

愚直に実装することで高々 O(NQY)O(NQY) で解くことができる．
しかし，特殊なケースをこのテストケースは含むため，特殊なケースの対応をしなければこの小課題にACすることはできない．

小課題2

ここで，発言を言い換える．
はじめに，NN 頂点 00 辺のグラフがあったとして，
「やっぱり，AA といったら BB だよねー」を「頂点 A−1A-1 から頂点 B−1B-1 に対して有向辺を結ぶ」，
「私さっき XX を YY 回連想したから，今思い浮かべている数字分かる？」を「頂点 X−1X-1 から YY 回移動したとき，今いる頂点に 11 足した値を出力せよ．ただし，今いる頂点が 11 つに定まらないときは -1 を出力せよ」と言い換えることにする．
このとき，この小課題では 11 回移動したときどの頂点に到達するかがはじめの入力によってすべて定まっているため，ダブリングを実装することでACすることができる．
実装については，はじめの NN 回の発言をすべて受け取ったのちにダブリングテーブルを埋めることで O(QlogY)O(QlogY) で解くことができる．
このテストケースは特殊なケースを含まない．

小課題3

小課題2の言い換えをそのまま用いて考える．
まとめてダブリングの前処理が行えなくなったため，前処理をほかの方法で行うための工夫をしなければならない．
このとき，更新手順は「 doubling[x][y]doubling[x][y] が −1-1 でなくなったとき，doubling[z][w]doubling[z][w] を更新する」という情報を持つ配列を作ることで，DFSなどにより，更新できる doublingdoubling のマスを逐一更新していくことができる．これにより Case1 の処理の合計を高々 O(NlogY)O(NlogY) に抑えることができる．

特殊なケースについて
まず，N=1N=1 のときは前述した通り，11 といえば 11 しかないことを考慮すればよい．
ここでは，2≤N2 \leq N のときの特殊なケースについて説明したい．
まず，相異なる整数 X,YX, Y について，頂点 X,YX, Y から有向辺が出ていないとき，つまり，有向辺が出ていない頂点が 22 つ以上存在するときのことを場合分けして考える．

1: XX は YY に，YY は YY に行くとき
すべての頂点について，ダブリングテーブルを用いて導出できない頂点の移動については，最後に頂点 XX か YY にたどり着いているものなので，X,YX, Y 両方についてのみ考えればよい．
ここで，今のように仮定すると，頂点 XX からは X→Y→Y→Y→Y…X→Y→Y→Y→Y… のように，頂点 YY からは Y→Y→Y→Y→Y…Y→Y→Y→Y→Y… のように遷移する．
2: XX は XX に，YY は XX に行くとき
11 と同様に考えると，頂点 XX からは X→X→X→X→X…X→X→X→X→X… のように，頂点 YY からは Y→X→X→X→X…Y→X→X→X→X… のように遷移する．
したがって 1,21, 2 より，確定した頂点まで移動した後は XX へ行くのか YY へ行くのか常に分からないため，特殊なケースは存在しない．

また，すべての頂点から有向辺が出ているとき，すべてどこへ行くかが確定するため特殊なケースは存在しない．
したがって，もし特殊なケースが存在するとしたら少なくとも「頂点 XX のみ有向辺が出ていない」を満たしている必要がある．以下ではすべてこれを仮定する．
ここで，もしいま分かっている有向辺のみでサイクルが存在しているときのことを考える．
サイクルが A1→A2→A3→⋯→As→A1→⋯A_1→A_2→A_3→⋯→A_s→A_1→⋯ のように遷移するとき，
X→A1→⋯X→A_1→⋯ という遷移と X→A2→⋯X→A_2→⋯ という遷移について考えると，どこへ行くか確定するケースは存在しないことが分かる．
そして，今あげたケースの条件をすべて満たさない場合のみ特殊なケースが存在し，そのとき，頂点 XX を通ることで成立するサイクルのうち，もっとも周期の長いサイクルの周期を SS ，頂点 AA から頂点 XX まで行くためにかかる移動の回数を YY として，11 から SS までの整数すべてで割り切れる整数のうち最小のもの EE を用いて，頂点 AA から E⋅x+YE \cdot x+Y 回動いた後は必ず頂点 XX にいることが分かる．
サイクル発見は O(N)O(N) でできるため，これで特殊なケースを実装できる．
実装についてはダブリングテーブルを実装し，以上の特殊なケースについても実装することでこの小課題にACすることができる．
このテストケースは特殊なケースを含む．

回答例(C++)

#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;
}

回答例(Python)

作成中！