test/yukicoder/497.test.cpp

View this file on GitHub
Last update: 2021-02-22 09:25:55+09:00
Problem: https://yukicoder.me/problems/no/497

Depends on

src/TopologicalSort.hpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/497"

#include "../../src/TopologicalSort.hpp"

#include <iostream>
#include <iomanip>
#include <array>

using namespace std;
using lint = long long;

struct init {
    init() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} init_;

int main() {

    int N;
    cin >> N;

    vector<array<int, 3>> xyz(N);
    for (int i = 0; i < N; i++) cin >> xyz[i][0] >> xyz[i][1] >> xyz[i][2];
    for (int i = 0; i < N; i++) sort(xyz[i].begin(), xyz[i].end());

    vector<vector<int>> edges(N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if ((xyz[i][0] < xyz[j][0]) &&
                (xyz[i][1] < xyz[j][1]) &&
                (xyz[i][2] < xyz[j][2]))
                edges[i].emplace_back(j);
        }
    }

    TopologicalSort ts(edges);
    ts.build();
    cout << ts.longest_path() + 1;

    return 0;
}

#line 1 "test/yukicoder/497.test.cpp"

#define PROBLEM "https://yukicoder.me/problems/no/497"

#line 2 "src/TopologicalSort.hpp"

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

using namespace std;

class TopologicalSort {
public:
    explicit TopologicalSort(int n) : edges(n), V(n), used(n) {}
    explicit TopologicalSort(const vector<vector<int>> &edges_) : edges(edges_), V(edges.size()), used(V) { }

    void add_edge(int from, int to) { edges[from].emplace_back(to); }

    vector<int> build() {
        vector<int> res, in(V);
        for (int i = 0; i < V; i++) for (const auto &e : edges[i]) in[e]++;

        res.reserve(V);
        queue<int> que;
        for (int i = 0; i < V; i++) {
            if (in[i] == 0 && !used[i]) {
                used[i] = 1;
                que.emplace(i);
            }
        }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            res.emplace_back(now);
            for (const auto &e : edges[now]) {
                in[e]--;
                if (in[e] == 0) {
                    if (used[e]) return vector<int>(); // unable to sort
                    used[e] = used[now] + 1;
                    que.emplace(e);
                }
            }
        }

        return res;
    }

    [[nodiscard]] int longest_path() {
        return *max_element(used.begin(), used.end()) - 1;
    }

private:
    vector<vector<int>> edges;
    int V;
    vector<int> used;
};
#line 5 "test/yukicoder/497.test.cpp"

#line 7 "test/yukicoder/497.test.cpp"
#include <iomanip>
#include <array>

using namespace std;
using lint = long long;

struct init {
    init() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} init_;

int main() {

    int N;
    cin >> N;

    vector<array<int, 3>> xyz(N);
    for (int i = 0; i < N; i++) cin >> xyz[i][0] >> xyz[i][1] >> xyz[i][2];
    for (int i = 0; i < N; i++) sort(xyz[i].begin(), xyz[i].end());

    vector<vector<int>> edges(N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if ((xyz[i][0] < xyz[j][0]) &&
                (xyz[i][1] < xyz[j][1]) &&
                (xyz[i][2] < xyz[j][2]))
                edges[i].emplace_back(j);
        }
    }

    TopologicalSort ts(edges);
    ts.build();
    cout << ts.longest_path() + 1;

    return 0;
}