結果
問題 |
No.1266 7 Colors
|
ユーザー |
|
提出日時 | 2020-10-23 22:16:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 199 ms / 3,000 ms |
コード長 | 1,759 bytes |
コンパイル時間 | 1,706 ms |
コンパイル使用メモリ | 172,540 KB |
実行使用メモリ | 101,140 KB |
最終ジャッジ日時 | 2024-07-21 10:51:56 |
合計ジャッジ時間 | 6,736 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Graph=vector<vector<int>>; typedef struct{ int par; int dep; int size; }node; node uft[7777777]; void resuf(){ int i; for(i=0;i<7777777;i++){ uft[i].par=i;uft[i].dep=0;uft[i].size=1; } return; } int find(int x){ if(uft[x].par==x){return x;} else{uft[x].par=find(uft[x].par);return uft[x].par;} } void uni(int x,int y){ int xp,yp; xp=find(x);yp=find(y); if(xp==yp){return;} if(uft[xp].dep>uft[yp].dep){ uft[yp].par=xp; uft[xp].size+=uft[yp].size; } else{ uft[xp].par=yp; uft[yp].size+=uft[xp].size; if(uft[xp].dep==uft[yp].dep){uft[yp].dep++;} } return; } int size(int x){ x=find(x); return uft[x].size; } int main(){ resuf(); int n,m,q; scanf("%d%d%d",&n,&m,&q); char s[131072][8]; for(int i=1;i<=n;i++){ scanf("%s",s[i]); for(int j=0;j<7;j++){ if(s[i][j]=='1' && s[i][(j+1)%7]=='1'){ uni(7*i+j,7*i+((j+1)%7)); } } } Graph g(n+1); for(int i=0;i<m;i++){ int u,v; scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); for(int j=0;j<7;j++){ if(s[u][j]=='1' && s[v][j]=='1'){ uni(7*u+j,7*v+j); } } } while(q>0){ q--; int t,a,b; scanf("%d%d%d",&t,&a,&b); if(t==1){ s[a][b-1]='1'; int i=a; for(int j=0;j<7;j++){ if(s[i][j]=='1' && s[i][(j+1)%7]=='1'){ uni(7*i+j,7*i+((j+1)%7)); } } int u=a; for(auto v: g[u]){ for(int j=0;j<7;j++){ if(s[u][j]=='1' && s[v][j]=='1'){ uni(7*u+j,7*v+j); } } } } else{ printf("%d\n",size(7*a)); } } }