結果

問題 No.1668 Grayscale
ユーザー qisnotnqqisnotnq
提出日時 2021-09-04 12:13:34
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,627 bytes
コンパイル時間 2,853 ms
コンパイル使用メモリ 214,856 KB
実行使用メモリ 79,232 KB
最終ジャッジ日時 2024-05-10 01:05:20
合計ジャッジ時間 8,735 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>

#define REP(i,n) for (int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()

using namespace std;

template <class T, class U> void amax(T& x, U y) {if (x < y) x = y;}

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

struct edge {
    typedef size_t weight_type;

    size_t m_to;

    edge(size_t to) : m_to(to) { }

    inline size_t to() const { return m_to; }

    inline weight_type weight() const { return 1; }

    friend std::ostream& operator<<(std::ostream &os, const edge &e) {
        os << "{ to: " << e.m_to << " }";
        return os;
    }
};

template <class Edge>
struct graph {
    using edge_type = Edge;

    const size_t m_n_vertices;
    std::vector<std::vector<edge_type>> m_edges;

    graph(size_t n_vertices) : m_n_vertices(n_vertices), m_edges(n_vertices) { }

    inline size_t n_vertices() const { return m_n_vertices; }

    inline void add_edge(size_t from, size_t to, typename edge_type::weight_type weight) {
        m_edges[from].emplace_back(to, weight);
    }

    inline void add_edge(size_t from, size_t to) {
        m_edges[from].push_back(to);
    }

    inline void add_edge(size_t from, const edge_type &e) {
        m_edges[from].emplace_back(e);
    }

    inline void add_biedge(size_t v0, size_t v1, typename edge_type::weight_type weight) {
        m_edges[v0].emplace_back(v1, weight);
        m_edges[v1].emplace_back(v0, weight);
    }

    inline void add_biedge(size_t v0, size_t v1) {
        m_edges[v0].push_back(v1);
        m_edges[v1].push_back(v0);
    }

    inline const std::vector<edge_type>& edges_from(size_t v) const {
        return m_edges[v];
    }
};

// if g has a cycle, return empty vector.
// Time complexity is O(V + E),
// where V is the number of vertices,
//       E is the number of edges.
template <class Graph>
std::vector<size_t> topological_sort(const Graph &g) {

    using Edge = typename Graph::edge_type;

    std::vector<size_t> topological_orders(g.n_vertices());
    std::vector<size_t> indegrees(g.n_vertices());

    for (size_t v = 0; v < g.n_vertices(); ++v) {
        for (const Edge &e: g.edges_from(v)) {
            ++indegrees[e.to()];
        }
    }

    std::queue<size_t> q;

    for (size_t v = 0; v < g.n_vertices(); ++v) {
        if (!indegrees[v]) {
            q.push(v);
        }
    }

    for (size_t i = 0; i < g.n_vertices(); ++i) {
        if (q.empty()) { // has cycle
            return { };
        }
        size_t u = q.front();
        q.pop();
        topological_orders[i] = u;
        for (const Edge &e: g.edges_from(u)) {
            size_t v = e.to();
            --indegrees[v];
            if (!indegrees[v]) {
                q.push(v);
            }
        }
    }

    return topological_orders;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    using Graph = graph<edge>;

    int H, W, N;
    cin >> H >> W >> N;
    vector<vector<int>> C(H, vector<int>(W));
    REP(i, H) REP(j, W) cin >> C[i][j];

    Graph g(H * W);
    REP(i, H) REP(j, W) {
        REP(k, 4) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (0 <= ni && ni < H && 0 <= nj && nj < W && C[i][j] < C[ni][nj]) {
                g.add_edge(i * H + j, ni * H + nj);
            }
        }
    }
    auto a = topological_sort(g);
    assert(a.size() == H * W);
    vector<int> dp(H * W);
    for (int i : a) {
        for (const edge &e : g.edges_from(i)) {
            int j = e.to();
            amax(dp[j], dp[i] + 1);
        }
    }
    int result = *max_element(all(dp)) + 1;
    cout << result << endl;

    return 0;
}
0