結果

問題 No.2639 Longest Increasing Walk
コンテスト
ユーザー 寝癖
提出日時 2024-02-19 23:03:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,887 bytes
コンパイル時間 1,381 ms
コンパイル使用メモリ 122,756 KB
実行使用メモリ 13,636 KB
最終ジャッジ日時 2024-09-29 02:45:32
合計ジャッジ時間 5,112 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

int main() {
    int H, W;
    std::cin >> H >> W;
    std::vector<std::vector<int>> A(H, std::vector<int>(W));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            std::cin >> A[i][j];
        }
    }

    std::vector<std::set<int>> to(H*W);
    for (int x = 0; x < H*W; ++x) {
        int i = x / W, j = x % W;
        int di[] = {1, 0, -1, 0};
        int dj[] = {0, 1, 0, -1};
        for (int k = 0; k < 4; ++k) {
            int ni = i + di[k], nj = j + dj[k];
            if (0 <= ni && ni < H && 0 <= nj && nj < W && A[ni][nj] > A[i][j]) {
                to[x].insert(ni*W+nj);
            }
        }
    }

    std::vector<int> indegree(H*W, 0);
    for (int x = 0; x < H*W; ++x) {
        for (auto y : to[x]) {
            indegree[y]++;
        }
    }

    std::queue<int> q;
    std::vector<int> B;
    for (int x = 0; x < H*W; ++x) {
        if (indegree[x] == 0) {
            q.push(x);
            B.push_back(x);
        }
    }

    std::vector<int> order;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        order.push_back(x);
        for (auto y : to[x]) {
            indegree[y]--;
            if (indegree[y] == 0) {
                q.push(y);
            }
        }
    }

    int ans = 0;
    for (auto x : B) {
        int i = std::find(order.begin(), order.end(), x) - order.begin();
        std::vector<int> dist(H*W, -1);
        dist[x] = 1;
        while (i < order.size()) {
            x = order[i++];
            for (auto y : to[x]) {
                if (dist[y] < dist[x] + 1) {
                    dist[y] = dist[x] + 1;
                }
            }
        }
        ans = std::max(ans, *std::max_element(dist.begin(), dist.end()));
    }

    std::cout << ans << std::endl;

    return 0;
}
0