結果
問題 |
No.1668 Grayscale
|
ユーザー |
![]() |
提出日時 | 2021-09-04 20:49:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,379 bytes |
コンパイル時間 | 4,527 ms |
コンパイル使用メモリ | 232,988 KB |
実行使用メモリ | 69,632 KB |
最終ジャッジ日時 | 2024-12-21 15:03:15 |
合計ジャッジ時間 | 9,131 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 8 WA * 14 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll=long long; using Graph=vector<vector<int>>; #define MAX 60 #define MOD 1000000007 #define INF 1000000000000000000 int main(){ int H,W,N; cin>>H>>W>>N; vector<vector<int>> C(H,vector<int>(W)); for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ cin>>C[i][j]; C[i][j]--; } } Graph G(N); vector<int> cnt(N,0); for(int i=0;i<H;i++){ for(int j=0;j<W-1;j++){ if(C[i][j]<C[i][j+1]){ G[C[i][j]].push_back(C[i][j+1]); cnt[C[i][j+1]]++; }else if(C[i][j]>C[i][j+1]){ G[C[i][j+1]].push_back(C[i][j]); cnt[C[i][j]]++; } } } for(int i=0;i<H-1;i++){ for(int j=0;j<W;j++){ if(C[i][j]<C[i+1][j]){ G[C[i][j]].push_back(C[i+1][j]); cnt[C[i+1][j]]++; }else if(C[i][j]>C[i+1][j]){ G[C[i+1][j]].push_back(C[i][j]); cnt[C[i][j]]++; } } } vector<int> length(N,0); queue<int> q; for(int i=0;i<N;i++){ if(cnt[i]==0){ q.push(i); } } while(!q.empty()){ int v=q.front(); q.pop(); for(auto nv:G[v]){ cnt[nv]--; length[nv]=max(length[nv],length[v]+1); if(cnt[nv]==0){ q.push(nv); } } } int ans=1; for(int i=0;i<N;i++){ ans=max(ans,length[i]+1); } cout<<ans<<'\n'; }