結果
問題 | No.1266 7 Colors |
ユーザー |
![]() |
提出日時 | 2020-10-24 14:56:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 346 ms / 3,000 ms |
コード長 | 2,099 bytes |
コンパイル時間 | 1,430 ms |
コンパイル使用メモリ | 122,772 KB |
最終ジャッジ日時 | 2025-01-15 15:06:06 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include<iostream>#include <cstring>#include<string>#include<algorithm>#include<vector>#include<iomanip>#include<math.h>#include<complex>#include<queue>#include<deque>#include<stack>#include<map>#include<set>#include<bitset>#include<functional>#include<assert.h>#include<numeric>using namespace std;#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )#define rep(i,n) REP(i,0,n)using ll = long long;const int inf=1e9+7;const ll longinf=1LL<<60 ;const ll mod=1e9+7 ;struct UnionFind{vector<int> par,siz;UnionFind(int N): par(N), siz(N){rep(i, N){par[i] = i; siz[i] = 1;}}int root(int x){if(par[x]==x) return x;else return root(par[x]);}void unite(int x, int y){x=root(x); y=root(y);if(x==y) return;if(siz[x] < siz[y]) swap(x, y);par[y] = x;siz[x] += siz[y];}bool same(int x, int y){return root(x)==root(y);}int size(int x){return siz[root(x)];}};int main(){int n, m, q; cin >> n >> m >> q; string s[n];rep(i, n) cin >> s[i];vector<int> to[n];rep(i, m){int u, v; cin >> u >> v; u--; v--;to[u].push_back(v); to[v].push_back(u);}UnionFind uf(7*n);rep(i, n){rep(j, 7){if(s[i][j]=='1' && s[i][(j+1)%7]=='1'){uf.unite(j*n+i, ((j+1)%7)*n+i); //cout << j*n+i << " " << ((j+1)%7)*n+i << endl;}if(s[i][j]=='1' && s[i][(j+7-1)%7]=='1'){uf.unite(j*n+i, ((j+7-1)%7)*n+i); //cout << j*n+i << " " << (j+7-1)%7 << endl;}for(auto k: to[i]){//cout << i << " " << k << endl;if(s[i][j]=='1' && s[k][j]=='1'){uf.unite(j*n+i, j*n+k); //cout << j*n+i << " " << j*n+k << endl;}}}}//cout << uf.size(0) << endl;rep(i, q){int a, x, y; cin >> a >> x >> y; x--; y--;if(a==1){s[x][y] = '1';if(s[x][(y+7-1)%7]=='1') uf.unite(y*n+x, ((y-1+7)%7)*n+x);if(s[x][(y+1)%7]=='1') uf.unite(y*n+x, ((y+1)%7)*n+x);for(auto k: to[x]){if(s[k][y]=='1') uf.unite(y*n+x, y*n+k);}}else{cout << uf.size(x) << endl;}}}