結果

問題 No.1266 7 Colors
ユーザー beet
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 HERE
signed 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0