結果

問題 No.497 入れ子の箱
ユーザー __Hyoga
提出日時 2017-03-28 18:33:58
言語 C++14
(gcc 7.2.0)
結果
AC  
実行時間 117 ms
コード長 1,118 Byte
コンパイル時間 1,072 ms
使用メモリ 4,296 KB
最終ジャッジ日時 2017-03-28 18:34:06

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 5 ms
1,548 KB
sample2.txt AC 3 ms
1,548 KB
sample3.txt AC 4 ms
1,552 KB
t01.txt AC 92 ms
4,260 KB
t02.txt AC 103 ms
4,268 KB
t03.txt AC 105 ms
4,268 KB
t04.txt AC 106 ms
4,260 KB
t05.txt AC 104 ms
4,264 KB
t06.txt AC 103 ms
4,296 KB
t07.txt AC 110 ms
4,264 KB
t08.txt AC 106 ms
4,264 KB
t09.txt AC 109 ms
4,260 KB
t10.txt AC 117 ms
3,048 KB
t11.txt AC 116 ms
2,984 KB
t12.txt AC 117 ms
2,968 KB
t13.txt AC 114 ms
3,024 KB
t14.txt AC 112 ms
3,044 KB
t15.txt AC 111 ms
2,988 KB
t16.txt AC 100 ms
4,232 KB
t17.txt AC 101 ms
4,228 KB
t18.txt AC 99 ms
4,228 KB
t19.txt AC 104 ms
4,228 KB
t20.txt AC 100 ms
4,228 KB
t21.txt AC 83 ms
1,604 KB
t22.txt AC 86 ms
1,600 KB
t23.txt AC 3 ms
1,544 KB
t24.txt AC 3 ms
1,548 KB
t25.txt AC 104 ms
3,580 KB
t26.txt AC 114 ms
3,584 KB
t27.txt AC 107 ms
3,548 KB
t28.txt AC 99 ms
1,604 KB
t29.txt AC 98 ms
1,644 KB
テストケース一括ダウンロード

ソースコード

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;
}
0