結果

問題 No.1266 7 Colors
ユーザー 小高悠太郎
提出日時 2025-09-11 00:05:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,753 bytes
コンパイル時間 3,735 ms
コンパイル使用メモリ 291,060 KB
実行使用メモリ 30,160 KB
最終ジャッジ日時 2025-09-11 00:06:05
合計ジャッジ時間 12,564 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i< (n); ++i)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define fore(i, a) for(auto &i:a)
using ll = long long;


struct UnionFind {
	vector<ll> ran;
	vector<ll> parent;
	vector<ll> siz;
	UnionFind(int n):ran(n, 0), parent(n), siz(n, 1){
		rep(i, n)parent[i] = i;
	}

	ll find(int x) {
		if(x == parent[x]) return x;
		return  parent[x] = find(parent[x]);
	}

	bool issame(int x, int y) {
		return find(x) == find(y);
	}

	void unite(int x, int y) {
		x = find(x); y = find(y);
		if(x == y) return;
		if(ran[x] < ran[y]) swap(x, y);
		parent[y] = x;
		if(ran[x] == ran[y]) ran[x]++;
		siz[x] += siz[y];
		return;
	}

	int size(int x) {
		return siz[find(x)];
	}
};
int main() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<string> s(n);
	rep(i, n) cin >> s[i];
	int N = 7*n;
	UnionFind uf(N);
	vector<vector<ll>> G(n);
	rep(i, m){
		int u, v;
		cin >> u >> v;
		u--;v--;
		G[u].push_back(v);
		G[v].push_back(u);
		rep(i, 7){
		  if(s[u][i] == '1' && s[v][i] == '1')uf.unite(i*n+u, i*n+v);
		}
	}
	rep(j, n){
		rep(i, 7){
			if(s[j][i] == '1' && s[j][(i+1)%7] == '1'){
        uf.unite(i*n+j, (i+1)%7*n+j);
			}
		}
	}
	vector<tuple<int,int,int>> qs(q);
	rep(i, q){
		int t, x, y;
		cin >> t >> x >> y;
		qs[i] = {t, --x, --y};
	}
  rep(i, q){
		auto[t, x, y] = qs[i];
		if(t == 1){
			if(s[x][(y+1)%7] == '1')uf.unite(y*n+x, (y+1)%7*n+x);
			if(s[x][(y-1)%7] == '1')uf.unite(y*n+x, (y+6)%7*n+x);
      fore(to, G[x]){
				if(s[to][y] == '1')uf.unite(y*n+x, y*n+to);
			}
		}
		else{
			cout << uf.size(0) << endl;
		}
	}

		
		




}
0