結果

問題 No.307 最近色塗る問題多くない？
ユーザー motimoti
提出日時 2015-11-28 00:27:49
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,629 bytes
コンパイル時間 1,190 ms
コンパイル使用メモリ 119,840 KB
実行使用メモリ 14,016 KB
最終ジャッジ日時 2024-09-14 00:42:17
合計ジャッジ時間 9,291 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
13,892 KB
testcase_01 AC 3 ms
6,944 KB
testcase_02 AC 3 ms
6,940 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 WA -
testcase_05 AC 3 ms
6,944 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 9 ms
6,944 KB
testcase_11 AC 18 ms
6,940 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 4 ms
6,944 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 52 ms
13,056 KB
testcase_28 TLE -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
権限があれば一括ダウンロードができます

ソースコード

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)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define minimize(a, x) a = std::min(a, x)
#define maximize(a, x) a = std::max(a, x)

using ll  = long long;
int const inf = 1<<29;

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[201*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;
}

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));
      }
    }
  }

/*
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\n\n";
*/

  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;
*/
/*
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";
*/

    auto& refCol = rootCol[RawPos];
    if(refCol != x) {
      refCol = x;
      vector<int> mv;
      for(auto& e: outers[RawPos]) {
        if(rootCol[uf.root(e)] == rootCol[RawPos]) {
          uf.unite(uf.root(e), RawPos);
          mv.push_back(uf.root(e));
        }
      }
/*
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\n";
*/
      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