結果

問題 No.1266 7 Colors
ユーザー motmot
提出日時 2020-10-24 00:20:12
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,394 ms / 3,000 ms
コード長 3,879 bytes
コンパイル時間 1,537 ms
コンパイル使用メモリ 104,192 KB
実行使用メモリ 69,028 KB
最終ジャッジ日時 2024-07-21 14:11:42
合計ジャッジ時間 19,036 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 420 ms
12,672 KB
testcase_04 AC 992 ms
45,896 KB
testcase_05 AC 488 ms
15,596 KB
testcase_06 AC 1,061 ms
51,200 KB
testcase_07 AC 1,161 ms
58,784 KB
testcase_08 AC 1,010 ms
47,260 KB
testcase_09 AC 842 ms
35,996 KB
testcase_10 AC 790 ms
31,964 KB
testcase_11 AC 560 ms
19,388 KB
testcase_12 AC 631 ms
23,540 KB
testcase_13 AC 726 ms
27,264 KB
testcase_14 AC 472 ms
15,336 KB
testcase_15 AC 1,120 ms
60,040 KB
testcase_16 AC 650 ms
24,496 KB
testcase_17 AC 1,121 ms
56,832 KB
testcase_18 AC 932 ms
69,028 KB
testcase_19 AC 1,237 ms
63,868 KB
testcase_20 AC 1,394 ms
63,872 KB
testcase_21 AC 231 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

pair<int, int> parent[7][100005];
int siz[7][100005];

pair<int, int> root(int x1, int x2) {
  if(x1==parent[x1][x2].fi && x2==parent[x1][x2].se) return mp(x1, x2);
  else return parent[x1][x2] = root(parent[x1][x2].fi, parent[x1][x2].se);
}

void unite(int x1, int x2, int y1, int y2) {
  pair<int, int> x, y;
  x = root(x1, x2);
  x1 = x.fi;
  x2 = x.se;
  y = root(y1, y2);
  y1 = y.fi;
  y2 = y.se;
  if(x1==y1 && x2==y2) return;
  if(siz[x1][x2]<siz[y1][y2]) {
    swap(x1, y1);
    swap(x2, y2);
  }
  parent[y1][y2] = mp(x1, x2);
  siz[x1][x2] += siz[y1][y2];
  return;
}

int main() {
  int N, M, Q;
  cin>>N>>M>>Q;
  vector<int> edge[N];
  string S[N];
  for(int i=0;i<N;++i) cin>>S[i];
  int u, v;
  for(int i=0;i<M;++i) {
    cin>>u>>v;
    u--;
    v--;
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  for(int i=0;i<7;++i) {
    for(int j=0;j<N;++j) {
      parent[i][j] = mp(i, j);
      siz[i][j] = 1;
    }
  }
  map<pair<int, int>, int> amap;
  queue<pair<int, int> > que;
  pair<int, int> state;
  int color, node;
  for(int i=0;i<7;++i) {
    for(int j=0;j<N;++j) {
      if(amap[mp(i, j)]>0 || S[j][i]=='0') continue;
      que.push(mp(i, j));
      while(!que.empty()) {
        state = que.front();que.pop();
        color = state.fi;
        node = state.se;
        if(amap[mp(color, node)]>0 || S[node][color]=='0') continue;
        amap[mp(color, node)] = 1;
        if(color==0) {
          if(S[node][1]=='1' && amap[mp(1, node)]==0) {
            unite(1, node, color, node);
            que.push(mp(1, node));
          }
          if(S[node][6]=='1' && amap[mp(6, node)]==0) {
            unite(6, node, color, node);
            que.push(mp(6, node));
          }
        }
        else if(color==6) {
          if(S[node][5]=='1' && amap[mp(5, node)]==0) {
            unite(5, node, color, node);
            que.push(mp(5, node));
          }
          if(S[node][0]=='1' && amap[mp(0, node)]==0) {
            unite(0, node, color, node);
            que.push(mp(0, node));
          }
        }
        else {
          if(S[node][color-1]=='1' && amap[mp(color-1, node)]==0) {
            unite(color-1, node, color, node);
            que.push(mp(color-1, node));
          }
          if(S[node][color+1]=='1' && amap[mp(color+1, node)]==0) {
            unite(color+1, node, color, node);
            que.push(mp(color+1, node));
          }
        }
        for(int k=0;k<edge[node].size();++k) {
          if(S[edge[node][k]][color]=='1' && amap[mp(color, edge[node][k])]==0) {
            unite(color, node, color, edge[node][k]);
            que.push(mp(color, edge[node][k]));
          }
        }
      }
    }
  }
  vector<int> ans;
  int query, x, y;
  for(int i=0;i<Q;++i) {
    cin>>query>>x>>y;
    x--;
    y--;
    if(query==1) {
      S[x][y] = '1';
      if(y==0) {
        if(S[x][1]=='1') unite(1, x, 0, x);
        if(S[x][6]=='1') unite(6, x, 0, x);
      }
      else if(y==6) {
        if(S[x][5]=='1') unite(5, x, 6, x);
        if(S[x][0]=='1') unite(0, x, 6, x);
      }
      else {
        if(S[x][y-1]=='1') unite(y-1, x, y, x);
        if(S[x][y+1]=='1') unite(y+1, x, y, x);
      }
      for(int j=0;j<edge[x].size();++j) {
        if(S[edge[x][j]][y]=='1') unite(y, x, y, edge[x][j]);
      }
    }
    else {
      ans.push_back(siz[root(0, x).fi][root(0, x).se]);
    }
  }
  for(int i=0;i<ans.size();++i) cout<<ans[i]<<endl;
}
0