結果

問題 No.1266 7 Colors
ユーザー polylogKpolylogK
提出日時 2020-10-23 22:46:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 165 ms / 3,000 ms
コード長 2,963 bytes
コンパイル時間 2,306 ms
コンパイル使用メモリ 202,952 KB
最終ジャッジ日時 2025-01-15 13:40:08
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
002.cpp: In function ‘int main()’:
002.cpp:62:11: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘union_find::size_type’ {aka ‘long int’} [-Wformat=]
002.cpp:20:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
002.cpp:26:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
002.cpp:50:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]

ソースコード

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