結果
問題 | No.1266 7 Colors |
ユーザー | butsurizuki |
提出日時 | 2020-10-23 22:15:23 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,757 bytes |
コンパイル時間 | 3,314 ms |
コンパイル使用メモリ | 168,772 KB |
実行使用メモリ | 13,860 KB |
最終ジャッジ日時 | 2023-09-28 16:06:25 |
合計ジャッジ時間 | 6,715 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
9,832 KB |
testcase_01 | AC | 5 ms
9,664 KB |
testcase_02 | AC | 5 ms
9,696 KB |
testcase_03 | AC | 118 ms
11,524 KB |
testcase_04 | AC | 171 ms
13,860 KB |
testcase_05 | AC | 127 ms
11,400 KB |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | AC | 166 ms
13,788 KB |
testcase_09 | AC | 158 ms
13,004 KB |
testcase_10 | AC | 154 ms
12,616 KB |
testcase_11 | AC | 131 ms
11,616 KB |
testcase_12 | AC | 134 ms
11,944 KB |
testcase_13 | AC | 144 ms
12,468 KB |
testcase_14 | AC | 124 ms
11,428 KB |
testcase_15 | RE | - |
testcase_16 | AC | 145 ms
12,272 KB |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | AC | 51 ms
10,568 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using Graph=vector<vector<int>>; typedef struct{ int par; int dep; int size; }node; node uft[524288]; void resuf(){ int i; for(i=0;i<524288;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)); } } }