東京工業大学プログラミングコンテスト2015 M - コインと無向グラフ

問題

頂点数n、辺数mの無向グラフが与えられ、グラフの各頂点iにはコインがc[i]枚乗っている
各プレイヤーは交互に以下の操作を繰り返す
1) 頂点0以外で頂点0と連結な頂点を1つ選び、それをjとする
2) jに隣接する頂点のうち、jより頂点0に近い点を1つ選び、それをkとする
3) jからkにコインを1枚以上移動する
先にコインを移動できなくなった方が負け
両者が最善を尽くすときどちらが勝つか

1 <= n <= 10^5
1 <= m <= 2*10^5
0 <= c[i] <= 10^8

解法

とりあえず頂点0からBFSして、各頂点への最短距離を求める
(ちなみにここで使わなかった辺は必要なくて、この辺を消すと頂点0を根とした根付き木になる)
するとこのゲームは、頂点0からの最短距離が奇数であるような頂点を山、それらに乗っているコインの数を石としたnimと見なすことができる
(距離が偶数の山に操作をしても返しのターンで元の状態に戻せるため)
xor和が0でなければ先手の勝ち、0なら後手の勝ち

int n, m, a[100100], d[100100], x, y, xo;
vector<int> e[100100];

signed main() {
	cin >> n >> m;
	rep(i,n) cin >> a[i];
	rep(i,m) {
		cin >> x >> y;
		e[x].push_back(y), e[y].push_back(x);
	}
	reps(i,1,n) d[i] = inf;
	queue<int> q;
	q.push(0);
	while (!q.empty()) {
		int v = q.front(); q.pop();
		each(i,e[v]) if (d[i]>d[v]+1) q.push(i), d[i] = d[v]+1;
	}
	rep(i,n) if (d[i]%2) xo ^= a[i];
	cout << (xo ? "First" : "Second") << endl;
}