結果

問題 No.1266 7 Colors
ユーザー mot
提出日時 2020-10-24 00:20:12
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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