結果
問題 | No.1266 7 Colors |
ユーザー |
![]() |
提出日時 | 2020-10-23 22:44:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 169 ms / 3,000 ms |
コード長 | 1,976 bytes |
コンパイル時間 | 2,470 ms |
コンパイル使用メモリ | 201,740 KB |
最終ジャッジ日時 | 2025-01-15 13:38:23 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h>using namespace std;using Int = long long;const char newl = '\n';template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}template<typename T=int>vector<T> read(size_t n){vector<T> ts(n);for(size_t i=0;i<n;i++) cin>>ts[i];return ts;}struct UnionFind{int num;vector<int> rs,ps;UnionFind(){}UnionFind(int n):num(n),rs(n,1),ps(n,0){iota(ps.begin(),ps.end(),0);}int find(int x){return (x==ps[x]?x:ps[x]=find(ps[x]));}bool same(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(rs[x]<rs[y]) swap(x,y);rs[x]+=rs[y];ps[y]=x;num--;}int size(int x){return rs[find(x)];}int count() const{return num;}};//INSERT ABOVE HEREsigned main(){cin.tie(0);ios::sync_with_stdio(0);int n,m,q;cin>>n>>m>>q;auto ss=read<string>(n);vector<vector<int>> G(n);for(int i=0;i<m;i++){int u,v;cin>>u>>v;u--;v--;G[u].emplace_back(v);G[v].emplace_back(u);}const int M = 7;UnionFind uf(M*n);auto idx=[&](int i,int j){return j*n+i;};for(int i=0;i<n;i++){for(int j=0;j<M;j++){if(ss[i][j]=='1' and ss[i][(j+1)%M]=='1')uf.unite(idx(i,j),idx(i,(j+1)%M));for(int k:G[i])if(ss[i][j]=='1' and ss[k][j]=='1')uf.unite(idx(i,j),idx(k,j));}}for(int i=0;i<q;i++){int t,x,y;cin>>t>>x>>y;x--;y--;if(t==1){ss[x][y]='1';for(int j=0;j<M;j++)if(ss[x][j]=='1' and ss[x][(j+1)%M]=='1')uf.unite(idx(x,j),idx(x,(j+1)%M));for(int z:G[x])if(ss[x][y]=='1' and ss[z][y]=='1')uf.unite(idx(x,y),idx(z,y));}if(t==2) cout<<uf.size(idx(x,0))<<newl;}return 0;}