結果

問題 No.307 最近色塗る問題多くない？
コンテスト
ユーザー moti
提出日時 2015-11-28 00:46:18
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,035 bytes
コンパイル時間 1,215 ms
コンパイル使用メモリ 117,376 KB
実行使用メモリ 15,260 KB
最終ジャッジ日時 2024-09-14 00:50:56
合計ジャッジ時間 7,146 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 4 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)

struct UnionFind
{
  vector<int> rank;
  vector<int> rid;

  UnionFind(int n) {
    rank.resize(n);
    rid.assign(n, -1);
  }

  void unite(int u, int v) {
    u = root(u), v = root(v);
    if(u == v) { return ; }
    if(rank[u] < rank[v]) {
      rid[u] = v;
    }
    else {
      rid[v] = u;
      if(rank[u] == rank[v]) {
        rank[u]++;
      }
    }
  }

  bool same(int u, int v) {
    return root(u) == root(v);
  }

  int root(int x) {
    if(rid[x] < 0) return x;
    else return rid[x] = root(rid[x]);
  }
};

int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};

int H, W;
int A[201][201];
int Q;
bool rootCol[200*200+1];
set<int> outers[200*200+1]; // []はroot

bool inrange(int y, int x) {
  return 0<=y&&y<H && 0<=x&&x<W;
}

inline int chpos(int y, int x) {
  return y*W+x;
}

#define DEBUG //debug(uf);
void debug(UnionFind& uf) {
cout << "v check ----------\n";
  rep(i, H) {
    rep(j, W) {
      if(j) cout << " ";
      cout << rootCol[uf.root(chpos(i, j))];
    }
    cout << endl;
  }
cout << "^ check ----------\n";
}

int main() {

  cin >> H >> W;

  rep(i, H) rep(j, W) {
    cin >> A[i][j];
    rootCol[chpos(i, j)] = A[i][j];
  }

  UnionFind uf(H * W + 1);

  rep(i, H) rep(j, W) {
    rep(k, 4) {
      int ni = i+dy[k], nj = j+dx[k];
      if(!inrange(ni, nj)) { continue; }
      if(A[i][j] == A[ni][nj]) {
        uf.unite(chpos(i, j), chpos(ni, nj));
        rootCol[uf.root(chpos(i, j))] = A[i][j];
      }
      else {
        outers[uf.root(chpos(i, j))].insert(chpos(ni, nj));
      }
    }
  }

  DEBUG

  cin >> Q;
  rep(_, Q) {
    int r, c, x;
    cin >> r >> c >> x; r--, c--;
    const int RawPos = uf.root(chpos(r, c));
/*
    cout << "rc outers" << r << ", " << c << endl;
    for(auto& e: outers[RawPos]) {
      cout << e << " ";
    }cout << endl;
*/
    DEBUG

    auto& refCol = rootCol[RawPos];
    if(refCol != x) {
      refCol = x;
      vector<int> mv;
      for(auto& e: outers[RawPos]) {
        if(rootCol[e] == rootCol[RawPos]) {
          uf.unite(e, RawPos);
          mv.push_back(e);
        }
      }

      DEBUG

      mv.push_back(RawPos);
      int rt = uf.root(RawPos);
      rep(i, mv.size()) {
        if(mv[i] == rt) { continue; }
        if (outers[rt].size() < outers[mv[i]].size()) { swap(outers[rt], outers[mv[i]]); }
        outers[rt].insert(outers[mv[i]].begin(), outers[mv[i]].end());
        outers[mv[i]].clear();
      }
    }
  }

  rep(i, H) {
    rep(j, W) {
      if(j) cout << " ";
      cout << rootCol[uf.root(chpos(i, j))];
    }
    cout << endl;
  }


  return 0;
}
0