第11回情オリ本選対策4日目

今日の目標

  • Segment Tree / BIT
  • (未)DPの巡回セールスマン読む
  • (未,0問)DP練習解けるだけ解く(>=4)
  • 食物連鎖解く

19:42-22:03

  • Craneも理解する程頭回ってないしこれ解くのにSegment Tree必要ですかねとか思ってしまうのでパス
  • バブルソートの交換回数もパス
  • POJ3468もパス
  • 平方分割もあとで読むが今はパス
  • きゅうりの頻出典型まとめもこれから解く物に含めよう
  • あかんJOI予選のBingoわからんかった、公式の解説みたら同値変形というかが自分で思いつく域でなかったので断念
  • 食物連鎖はじめて解こうとしたら予想外にむずかった、しかもあまり納得できていない。こういう論理的な何か苦手
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

class UnionFind {
private:
	vector<int> data;
public:
	UnionFind(int size) : data(size, -1) {}
	int root(int x) {
		if (data[x] < 0)
			return x;
		return root(data[x]);
	}

	bool same(int x, int y) {
		return root(x) == root(y);
	}

	void unite(int x, int y) {
		int xIdx = root(x), yIdx = root(y);
		int xHeight = -data[xIdx], yHeight = -data[yIdx];
		if (xHeight < yHeight) {
			swap (xIdx, yIdx);
			swap (xHeight, yHeight);
		}
		// so xHeight > yHeight
		data[yIdx] = xIdx;
		data[xIdx] = -max(xHeight, yHeight + 1);
		return;
	}
};
int main()
{
	int N, K;
	scanf("%d %d\n", &N, &K);

	UnionFind uf(N * 3);
	/* 0 ~ (N - 1) : X-A
	 * N ~ (2N - 1) : X-B
	 * 2N ~ (3N - 1) : X-C
	 */

	int res = 0;
	for (int h = 0; h < K; ++h) {
		int D, X, Y;
		scanf("%d %d %d\n", &D, &X, &Y);
		if (!(1 <= X && X <= N) || !(1 <= Y && Y <= N)) {
			res++;
			continue;
		}
		X--, Y--;
		if (D == 1) { // X and Y are the same species.
			if (uf.same(X, N + Y)
			 || uf.same(X, 2 * N + Y)) {
				res++;
			} else {
				uf.unite(X, Y);
				uf.unite(N + X, N + Y);
				uf.unite(2 * N + X, 2 * N + Y);
			}
		} else { // X eats Y
			if (uf.same(X, Y)
			 || uf.same(X, 2 * N + Y)) {
				res++;
			} else {
				uf.unite(X, N + Y);
				uf.unite(N + X, 2 * N + Y);
				uf.unite(2 * N + X, Y);
			}
		}
	}
	printf("%d\n", res);
	return 0;
}

おい…今日1問しか解いてねーぞ…(眺めた問題は多し)
絶対的能力とかがないので上位陣の方々みたいにポンポン解けないんすよねー
まだまだ体力的には解けるけど明日もあるので寝る
のんびりメシを食いのんびり風呂に入るというのは確実に実時間を削っている