結果

問題 No.1266 7 Colors
ユーザー polylogKpolylogK
提出日時 2020-10-23 22:46:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 173 ms / 3,000 ms
コード長 2,963 bytes
コンパイル時間 2,785 ms
コンパイル使用メモリ 206,856 KB
実行使用メモリ 18,428 KB
最終ジャッジ日時 2023-09-28 17:06:07
合計ジャッジ時間 6,633 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 92 ms
6,836 KB
testcase_04 AC 145 ms
13,820 KB
testcase_05 AC 95 ms
7,360 KB
testcase_06 AC 155 ms
15,040 KB
testcase_07 AC 161 ms
16,416 KB
testcase_08 AC 168 ms
14,160 KB
testcase_09 AC 126 ms
11,804 KB
testcase_10 AC 124 ms
11,124 KB
testcase_11 AC 107 ms
8,440 KB
testcase_12 AC 111 ms
9,212 KB
testcase_13 AC 120 ms
9,948 KB
testcase_14 AC 98 ms
7,372 KB
testcase_15 AC 165 ms
16,684 KB
testcase_16 AC 116 ms
9,396 KB
testcase_17 AC 173 ms
16,420 KB
testcase_18 AC 93 ms
18,428 KB
testcase_19 AC 92 ms
18,044 KB
testcase_20 AC 93 ms
17,968 KB
testcase_21 AC 48 ms
4,876 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "002.cpp"
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

#line 1 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/union_find.hpp"



#line 6 "/home/ecasdqina/cpcpp/libs/library_cpp/data_structure/union_find.hpp"

class union_find {
public:
	using size_type = std::int_fast32_t;
	using container = std::vector<size_type>;
	
	container data;
	size_type comp_cnt;

private:
	const size_type find(size_type k) {
		if(data[k] < 0) return k;
		return data[k] = find(data[k]);
	}

public:
	union_find() = default;
	union_find(const union_find &) = default;
	union_find(union_find&&) = default;

	union_find & operator=(const union_find &) = default;
	union_find & operator=(union_find &&) = default;

	union_find(size_type N): data(N, -1), comp_cnt(N) {}

	bool unite(size_type x, size_type y) {
		x = find(x); y = find(y);
		if(x == y) return false;
		if(data[x] > data[y]) std::swap(x, y);
		
		data[x] += data[y];
		data[y] = x;
		comp_cnt--;
		return true;
	}
	
	bool is_united(size_type x, size_type y) { return find(x) == find(y); }
	size_type size() const { return data.size(); }
	size_type size(size_type k) { return -data[find(k)]; }
	size_type comp(size_type k) { return find(k); };
	size_type count() const { return comp_cnt; }
	size_type operator[](size_type k) { return find(k); }
	
	void swap(union_find & r) {
		data.swap(r.data);
		std::swap(comp_cnt, r.comp_cnt);
	}
};


#line 18 "002.cpp"

int main() {
	int n, m, q; scanf("%d%d%d", &n, &m, &q);
	std::vector<std::string> color(n);
	std::vector<int> x(m), y(m);
	std::vector<std::vector<int>> g(n);
	for(int i = 0; i < n; i++) std::cin >> color[i];
	for(int i = 0; i < m; i++) {
		scanf("%d%d", &x[i], &y[i]);
		x[i]--; y[i]--;

		g[x[i]].push_back(i);
		g[y[i]].push_back(i);
	}

	union_find uf(n * 7);
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < 7; j++) {
			if(color[i][j] == '1' and color[i][(j + 1) % 7] == '1') {
				uf.unite(j * n + i, (j + 1) % 7 * n + i);
			}
		}
	}
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < 7; j++) {
			if(color[x[i]][j] == '1' and color[y[i]][j] == '1') {
				uf.unite(j * n + x[i], j * n + y[i]);
			}
		}
	}

	while(q--) {
		int type, a, b; scanf("%d%d%d", &type, &a, &b); a--; b--;

		if(type == 1) {
			color[a][b] = '1';
			if(color[a][(b + 6) % 7] == '1') uf.unite(b * n + a, (b + 6) % 7 * n + a);
			if(color[a][(b + 1) % 7] == '1') uf.unite(b * n + a, (b + 1) % 7 * n + a);
			for(auto id: g[a]) {
				int to = x[id] ^ y[id] ^ a;
				if(color[to][b] != '1') continue;
				uf.unite(b * n + a, b * n + to);
			}
		} else if(type == 2) {
			printf("%d\n", uf.size(a));
		}
	}
	return 0;
}
0