結果

問題 No.497 入れ子の箱
コンテスト
ユーザー vjudge1
提出日時 2025-02-22 16:48:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 5,000 ms
コード長 1,519 bytes
コンパイル時間 2,387 ms
コンパイル使用メモリ 200,436 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-22 16:48:31
合計ジャッジ時間 4,189 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
//#define int long long
using namespace std;
inline int read()
{
   int x=0,f=1;char ch=getchar();
   while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
   while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
   return x*f;
}
void write(int x)
{
   if(x<0)putchar('-'),x=-x;
   if(x<10)putchar(x+'0');
   else write(x/10),putchar(x%10+'0');
}
const int N=2e3;
const int mod=1e9+7;
vector<int>g[N];
int n;
struct node{
	int x,y,z;
}box[N];
int rans;
bool fl[N];
int rd[N];
int dp[N];
queue<int>q;
signed main(){
//	freopen("box.in","r",stdin);
//	freopen("box.out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i){
		int x=read(),y=read(),z=read();
		box[i].x=x;
		box[i].y=y;
		box[i].z=z;
		if(box[i].x>box[i].z)swap(box[i].x,box[i].z);
		if(box[i].y>box[i].z)swap(box[i].y,box[i].z);
		if(box[i].x>box[i].y)swap(box[i].x,box[i].y);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			if(box[i].x>box[j].x&&box[i].y>box[j].y&&box[i].z>box[j].z)rd[j]++,g[i].push_back(j);
		}
	}
	for(int i=1;i<=n;++i)g[0].push_back(i),rd[i]++;
	q.push(0);
	dp[0]=0;
	fl[0]=1;
	while(!q.empty()){
		int t=q.front();
		q.pop();
		for(int i=0;i<g[t].size();i++){
			if(fl[t]){
				if(!fl[g[t][i]])fl[g[t][i]]=1,dp[g[t][i]]=dp[t]+1;
				else dp[g[t][i]]=max(dp[g[t][i]],dp[t]+1);
			}
		//	cout<<t<<" "<<g[t][i]<<" "<<dp[g[t][i]]<<"\n";
			rd[g[t][i]]--;
			if(!rd[g[t][i]])q.push(g[t][i]);
		}
	}
	 for(int i=1;i<=n;i++)rans=max(rans,dp[i]);
	 cout<<rans<<"\n";
    return 0;
}
0