結果

問題 No.497 入れ子の箱
ユーザー legendcn
提出日時 2025-02-25 23:13:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 35 ms / 5,000 ms
コード長 1,437 bytes
コンパイル時間 2,036 ms
コンパイル使用メモリ 170,416 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-25 23:13:30
合計ジャッジ時間 3,652 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:22:11: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   22 |     scanf ("%d", &n);
      |     ~~~~~~^~~~~~~~~~
main.cpp:25:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   25 |         scanf ("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

# include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
// # define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
const int N = 1005;

int n;
struct node
{
    int x, y, z;
} a[N];
vector <int> e[N];
int ind[N];
int f[N];
signed main ()
{
    // freopen ("box.in", "r", stdin); freopen ("box.out", "w", stdout);
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf ("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
        vector <int> vec;
        vec.push_back (a[i].x); vec.push_back (a[i].y); vec.push_back (a[i].z);
        sort (vec.begin (), vec.end ());
        a[i].x = vec[0], a[i].y = vec[1], a[i].z = vec[2];
    }
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= n; j ++ )
        {
            if (a[i].x < a[j].x && a[i].y < a[j].y && a[i].z < a[j].z)
                e[i].push_back (j), ind[j] ++ ;
        }
    }
    queue <int> q;
    for (int i = 1; i <= n; i ++ )
    {
        if (!ind[i])
        {
            q.push (i);
            f[i] = 1;
        }
    }
    while (!q.empty ())
    {
        int u = q.front (); q.pop ();
        for (auto v : e[u])
        {
            if (!( -- ind[v]))
            {
                q.push (v);
                f[v] = f[u] + 1;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i ++ ) ans = max (ans, f[i]);
    printf ("%d\n", ans);
    return 0;
}
0