結果

問題 No.1668 Grayscale
ユーザー ripityripity
提出日時 2024-11-23 20:48:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,755 bytes
コンパイル時間 2,486 ms
コンパイル使用メモリ 217,784 KB
実行使用メモリ 73,728 KB
最終ジャッジ日時 2024-11-23 20:49:15
合計ジャッジ時間 6,303 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 WA -
testcase_05 AC 1 ms
5,248 KB
testcase_06 WA -
testcase_07 AC 465 ms
73,600 KB
testcase_08 AC 199 ms
42,368 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 1 ms
5,248 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#include <atcoder/dsu>
using namespace atcoder;

int main() {
  int H, W, N;
  cin >> H >> W >> N;
  vector C(H, vector<int>(W));
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      cin >> C[i][j];
    }
  }
  dsu uf(H * W);
  for(int i = 0; i < H; i++) {
    for(int j = 1; j < W; j++) {
      const int x = W * i + j;
      const int y = W * i + (j - 1);
      if(C[i][j] == C[i][j - 1]) uf.merge(x, y);
    }
  }
  for(int i = 1; i < H; i++) {
    for(int j = 0; j < W; j++) {
      const int x = W * i + j;
      const int y = W * (i - 1) + j;
      if(C[i][j] == C[i - 1][j]) uf.merge(x, y);
    }
  }
  vector<int> d(H * W);
  vector<vector<int>> G(H * W);
  for(int i = 0; i < H; i++) {
    for(int j = 1; j < W; j++) {
      const int x = uf.leader(W * i + j);
      const int y = uf.leader(W * i + (j - 1));
      if(uf.same(x, y)) continue;
      if(C[i][j] < C[i][j - 1]) G[x].push_back(y), d[y]++;
      if(C[i][j] > C[i][j - 1]) G[y].push_back(x), d[x]++;
    }
  }
  for(int i = 1; i < H; i++) {
    for(int j = 0; j < W; j++) {
      const int x = uf.leader(W * i + j);
      const int y = uf.leader(W * (i - 1) + j);
      if(uf.same(x, y)) continue;
      if(C[i][j] < C[i - 1][j]) G[x].push_back(y), d[y]++;
      if(C[i][j] > C[i - 1][j]) G[y].push_back(x), d[x]++;
    }
  }
  queue<int> que;
  vector<int> dp(H * W);
  for(int i = 0; i < H * W; i++) {
    if(i == uf.leader(i) && d[i] == 0) que.push(i);
  }
  while(!que.empty()) {
    int x = que.front();
    que.pop();
    for(int y : G[x]) {
      d[y]--;
      if(d[y] == 0) {
        dp[y] = max(dp[y], dp[x] + 1);
        que.push(y);
      }
    }
  }
  cout << 1 + *max_element(dp.begin(), dp.end()) << endl;
}
0