結果
問題 | No.1266 7 Colors |
ユーザー | kyoprouno |
提出日時 | 2020-10-24 00:05:38 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 391 ms / 3,000 ms |
コード長 | 3,762 bytes |
コンパイル時間 | 2,279 ms |
コンパイル使用メモリ | 187,292 KB |
実行使用メモリ | 28,880 KB |
最終ジャッジ日時 | 2023-09-28 19:24:41 |
合計ジャッジ時間 | 10,054 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 9 ms
19,296 KB |
testcase_01 | AC | 10 ms
19,116 KB |
testcase_02 | AC | 10 ms
19,180 KB |
testcase_03 | AC | 265 ms
23,116 KB |
testcase_04 | AC | 371 ms
26,540 KB |
testcase_05 | AC | 272 ms
23,256 KB |
testcase_06 | AC | 370 ms
27,192 KB |
testcase_07 | AC | 381 ms
27,796 KB |
testcase_08 | AC | 361 ms
26,864 KB |
testcase_09 | AC | 339 ms
25,404 KB |
testcase_10 | AC | 331 ms
25,164 KB |
testcase_11 | AC | 295 ms
23,524 KB |
testcase_12 | AC | 307 ms
24,044 KB |
testcase_13 | AC | 326 ms
24,692 KB |
testcase_14 | AC | 273 ms
22,988 KB |
testcase_15 | AC | 391 ms
28,360 KB |
testcase_16 | AC | 316 ms
24,172 KB |
testcase_17 | AC | 377 ms
27,660 KB |
testcase_18 | AC | 268 ms
28,880 KB |
testcase_19 | AC | 167 ms
27,940 KB |
testcase_20 | AC | 168 ms
27,996 KB |
testcase_21 | AC | 231 ms
21,584 KB |
ソースコード
#pragma GCC optimize("O3") #include <bits/stdc++.h> #define ll long long #define rep(i,n) for(int i=0;i<(n);i++) #define pll pair<ll,ll> #define pii pair<int,int> #define pq priority_queue #define pb push_back #define eb emplace_back #define fi first #define se second #define endl '\n' #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define lb(c,x) distance(c.begin(),lower_bound(all(c),x)) #define ub(c,x) distance(c.begin(),upper_bound(all(c),x)) using namespace std; const ll INF=1e9+10; class DisjointSet{ public: vector<ll> rank,p,sz; DisjointSet(){} DisjointSet(ll size){ //作られうる木の頂点数の最大値を入れる。 rank.resize(size,0); p.resize(size,0); sz.resize(size,1); rep(i,size) makeSet(i); } void makeSet(ll x){ //xだけが属する木を作る。 p[x]=x; rank[x]=0; } bool same(ll x,ll y){ //xとyが同じ木に属するかどうか return findSet(x)==findSet(y); } void unite(ll x, ll y){ link(findSet(x),findSet(y)); } void link(ll x, ll y){ //rankが大きい方の根に小さい方の根をつける。 if(rank[x]>rank[y]){ p[y]=x; } else{ p[x]=y; if(rank[x]==rank[y]){ rank[y]++; //xとyの木のrankが同じであれば、統合するとrankが1増える。 } } sz[x]+=sz[y]; sz[y]=sz[x]; } ll findSet(ll x){ //xが属する木の根の番号を返す if(x!=p[x]){ p[x]=findSet(p[x]); } return p[x]; } }; DisjointSet ds=DisjointSet(700005); vector<vector<ll>> to; /*void dfs(ll v,ll p=-1){ for(auto x:to[v]){ if(x==p) continue; if(ds.same(x,v)) continue; } return ; }*/ int main(){ ll n,m,q; cin >> n >> m >> q; vector<string> s(n); to=vector<vector<ll>>(n); rep(i,n){ cin >> s[i]; } rep(i,m){ ll u,v; cin >> u >> v; u--, v--; to[u].push_back(v); to[v].push_back(u); rep(j,7){ if(s[u][j]=='1' && s[v][j]=='1'){ ll from=7*u+j; ll go=7*v+j; if(!ds.same(from,go)){ ds.unite(from,go); } } } } rep(i,n){ rep(j,7){ if(s[i][j]=='1' && s[i][(j+1)%7]=='1'){ ll from=7*i+j; ll go=7*i+((j+1)%7); if(!ds.same(from,go)){ ds.unite(from,go); } } } } rep(i,q){ ll t; cin >> t; if(t==1){ ll x,y; cin >> x >> y; x--; y--; s[x][y]='1'; ll pre=(y-1+7)%7; ll nxt=(y+1)%7; if(s[x][pre]=='1'){ ll from=7*x+pre; ll go=7*x+y; if(!ds.same(from,go)){ ds.unite(from,go); } } if(s[x][nxt]=='1'){ ll from=7*x+nxt; ll go=7*x+y; if(!ds.same(from,go)){ ds.unite(from,go); } } for(auto w:to[x]){ if(s[w][y]=='1'){ ll from=7*w+y; ll go=7*x+y; if(!ds.same(from,go)){ ds.unite(from,go); } } } } if(t==2){ ll x,buf; cin >> x >> buf; x--; ll node=7*x; cout << ds.sz[ds.findSet(node)] << endl; } } return 0; }