結果

問題 No.497 入れ子の箱
ユーザー fiord
提出日時 2017-03-28 18:33:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 69 ms / 5,000 ms
コード長 1,118 bytes
コンパイル時間 811 ms
コンパイル使用メモリ 84,924 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2024-07-06 13:27:03
合計ジャッジ時間 3,219 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> edge[1010];
int rest[1010];
int depth[1010];
bool contain(vector<int> a, vector<int> b) {
    do {
        if (a[0] > b[0] && a[1] > b[1] && a[2] > b[2])  return true;
    } while (next_permutation(b.begin(), b.end()));
    return false;
}
int main() {
    int n;  cin >> n;
    vector<vector<int>> dat(n, vector<int>(3));
    for (int i = 0; i < n; i++) {
        cin >> dat[i][0] >> dat[i][1] >> dat[i][2];
        sort(dat[i].begin(), dat[i].end());
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (contain(dat[i], dat[j])) {
                edge[i].push_back(j);
                rest[j]++;
            }
        }
    }
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (rest[i] == 0) {
            depth[i] = 1;
            q.push(i);
        }
    }
    while (!q.empty()) {
        int cur = q.front();    q.pop();
        for (int i = 0; i < edge[cur].size(); i++){
            int to = edge[cur][i];
            depth[to] = max(depth[to], depth[cur] + 1);
            rest[to]--;
            if (rest[to] == 0)  q.push(to);
        }
    }
    int ret = 0;
    for (int i = 0; i < n; i++) ret = max(ret, depth[i]);
    cout << ret << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0