結果

問題 No.1668 Grayscale
ユーザー ripity
提出日時 2024-11-23 20:48:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,755 bytes
コンパイル時間 2,611 ms
コンパイル使用メモリ 210,948 KB
最終ジャッジ日時 2025-02-25 06:00:53
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 7 WA * 15
権限があれば一括ダウンロードができます

ソースコード

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