結果
| 問題 | No.497 入れ子の箱 |
| ユーザー |
|
| 提出日時 | 2017-03-25 00:07:03 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 199 ms / 5,000 ms |
| コード長 | 8,743 bytes |
| コンパイル時間 | 1,876 ms |
| コンパイル使用メモリ | 181,416 KB |
| 実行使用メモリ | 9,856 KB |
| 最終ジャッジ日時 | 2024-07-06 02:54:11 |
| 合計ジャッジ時間 | 4,929 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 29 |
ソースコード
#ifdef __MAI#include <cassert>#include <cctype>#include <cerrno>#include <cfloat>#include <ciso646>#include <climits>#include <clocale>#include <cmath>#include <csetjmp>#include <csignal>#include <cstdarg>#include <cstddef>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <ccomplex>#include <cfenv>#include <cinttypes>//#include <cstdalign>#include <cstdbool>#include <cstdint>#include <ctgmath>#include <cwchar>#include <cwctype>#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <exception>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iosfwd>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <locale>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <set>#include <sstream>#include <stack>#include <stdexcept>#include <streambuf>#include <string>#include <typeinfo>#include <utility>#include <valarray>#include <vector>#include <array>#include <atomic>#include <chrono>#include <condition_variable>#include <forward_list>#include <future>#include <initializer_list>#include <mutex>#include <random>#include <ratio>#include <regex>#include <scoped_allocator>#include <system_error>#include <thread>#include <tuple>#include <typeindex>#include <type_traits>#include <unordered_map>#include <unordered_set>#else#include <bits/stdc++.h>#endifusing namespace std;typedef unsigned int uint;typedef long long int ll;typedef unsigned long long int ull;#define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;#define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;}#define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;#define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;}#define debugaar(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}#define ALL(v) (v).begin(),(v).end()#define BIGINT 0x7FFFFFFF#define E107 1000000007llvoid printbit(int u) { if (u == 0)cout << 0; else { int s = 0, k = 0; for (; 0<u; u >>= 1, k++)s = (s << 1) | (u & 1); for (; 0<k--; s >>= 1)cout <<(s & 1); } }#define TIME chrono::system_clock::now()#define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count())namespace {std::chrono::system_clock::time_point t;void tic() { t = TIME; }void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - t)); }std::chrono::system_clock::time_point tle = TIME;#ifdef __MAIvoid safe_tle(int msec) { assert(MILLISEC(TIME - tle) < msec); }#else#define safe_tle(k) ;#endif}template<typename T1, typename T2>ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o; }random_device noize; // noizemt19937 mt(noize());int rand_int(int l, int h) {uniform_int_distribution<> range(l, h);return range(mt);}#ifndef __MAInamespace {class MaiScanner {public:template<typename T>void input_integer(T& var) {var = 0;T sign = 1;int cc = getchar_unlocked();for (; cc<'0' || '9'<cc; cc = getchar_unlocked())if (cc == '-') sign = -1;for (; '0' <= cc&&cc <= '9'; cc = getchar_unlocked())var = (var << 3) + (var << 1) + cc - '0';var = var*sign;}void ign() { getchar_unlocked(); }MaiScanner& operator>>(int& var) {input_integer<int>(var);return *this;}MaiScanner& operator>>(long long& var) {input_integer<long long>(var);return *this;}};class MaiPrinter {int stack_p;char stack[32];public:template<typename T>void output_integer(T var) {if (var == 0) {putchar_unlocked('0');return;}if (var < 0) {putchar_unlocked('-');var = -var;}stack_p = 0;while (var) {stack[stack_p++] = '0' + (var % 10);var /= 10;}while (stack_p)putchar_unlocked(stack[--stack_p]);}MaiPrinter& operator<<(char c) {putchar_unlocked(c);return *this;}MaiPrinter& operator<<(int var) {output_integer<int>(var);return *this;}MaiPrinter& operator<<(long long var) {output_integer<long long>(var);return *this;}};}MaiScanner scanner;MaiPrinter printer;#else#define scanner cin#endifclass Graph {public:class adjacent {public:Graph& g;int id;adjacent(Graph& g, int id) :g(g), id(id) {}class iterator {public:adjacent& ref;int pointer;iterator(adjacent& ref, int p = 0) :ref(ref), pointer(p) {}iterator& operator ++() {++pointer; return *this;}const int& operator*() const {int n1 = ref.g.vertex_to[ref.id].size();return pointer<n1 ? ref.g.vertex_to[ref.id][pointer] : ref.g.vertex_from[ref.id][pointer - n1];}int& operator*() {int n1 = ref.g.vertex_to[ref.id].size();return pointer<n1 ? ref.g.vertex_to[ref.id][pointer] : ref.g.vertex_from[ref.id][pointer - n1];}bool operator!=(const iterator& it) const {return it.pointer != pointer;}};iterator begin() { return iterator(*this, 0); }iterator end() { return iterator(*this, g.vertex_to[id].size() + g.vertex_from[id].size()); }};size_t n;vector<vector<int>> vertex_to;vector<vector<int>> vertex_from;Graph(size_t n) :n(n), vertex_to(n), vertex_from(n) {}void connect(int from, int to) {vertex_to[from].emplace_back(to);vertex_from[to].emplace_back(from);}void resize(size_t _n) {n = _n;vertex_to.resize(_n);vertex_from.resize(_n);}// for (auto to : g.vertex_adjacent(vertex_id)) な感じで使うadjacent vertex_adjacent(int idx) {return adjacent(*this, idx);}size_t degree(int v) {return vertex_to[v].size() + vertex_from[v].size();}void reverse_direction() {vertex_from.swap(vertex_to);}};/* ============ */int n, m, kei;int width, height;int field[111][111];int gx, gy;//pair<double,int> kuri[111];int hako[1010][3];int hakodp[1010][1010];Graph g(1);int ahodfs(int u) {int r = 1;fprintf(stderr, "%d\n", u);for (int v : g.vertex_to[u]) {r = max(r, ahodfs(v) + 1);}//fprintf(stderr,"%d\n",r);return r;}int main() {int i, j, k;int x, y, z;int a, b, c, d;scanner >> n;g.resize(n);for (i = 0; i < n; ++i) {scanner >> x >> y >> z;hako[i][0] = x;hako[i][1] = y;hako[i][2] = z;}for (i = 0; i < n; ++i) {for (j = 0; j < n; ++j) {if ((hako[i][0] < hako[j][0] && hako[i][1] < hako[j][1] && hako[i][2] < hako[j][2]) ||(hako[i][0] < hako[j][0] && hako[i][1] < hako[j][2] && hako[i][2] < hako[j][1]) ||(hako[i][0] < hako[j][1] && hako[i][1] < hako[j][0] && hako[i][2] < hako[j][2]) ||(hako[i][0] < hako[j][1] && hako[i][1] < hako[j][2] && hako[i][2] < hako[j][0]) ||(hako[i][0] < hako[j][2] && hako[i][1] < hako[j][0] && hako[i][2] < hako[j][1]) ||(hako[i][0] < hako[j][2] && hako[i][1] < hako[j][1] && hako[i][2] < hako[j][0])) {g.connect(i, j);}}}//visit.resize(n);vector<int> rank(n,1);int result = 1;for (int u = 0; u < n; ++u) {queue<int> q;q.push(u);while (!q.empty()) {k = q.front();q.pop();for (int v : g.vertex_to[k]) {if (rank[v] < rank[k] + 1){rank[v] = rank[k] + 1;result = max(result, rank[v]);q.push(v);}}}}cout << result << endl;return 0;}