結果
問題 | No.2179 Planet Traveler |
ユーザー | t98slider |
提出日時 | 2023-01-06 23:41:33 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 487 ms / 3,000 ms |
コード長 | 4,608 bytes |
コンパイル時間 | 2,012 ms |
コンパイル使用メモリ | 180,916 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-05-07 23:41:13 |
合計ジャッジ時間 | 8,410 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 3 ms
6,944 KB |
testcase_11 | AC | 102 ms
6,940 KB |
testcase_12 | AC | 476 ms
6,944 KB |
testcase_13 | AC | 486 ms
6,944 KB |
testcase_14 | AC | 93 ms
6,940 KB |
testcase_15 | AC | 90 ms
6,940 KB |
testcase_16 | AC | 93 ms
6,944 KB |
testcase_17 | AC | 487 ms
6,940 KB |
testcase_18 | AC | 484 ms
6,944 KB |
testcase_19 | AC | 484 ms
6,940 KB |
testcase_20 | AC | 64 ms
6,940 KB |
testcase_21 | AC | 447 ms
6,944 KB |
testcase_22 | AC | 303 ms
6,944 KB |
testcase_23 | AC | 257 ms
6,940 KB |
testcase_24 | AC | 377 ms
6,944 KB |
testcase_25 | AC | 293 ms
6,944 KB |
testcase_26 | AC | 415 ms
6,940 KB |
testcase_27 | AC | 64 ms
6,944 KB |
testcase_28 | AC | 198 ms
6,944 KB |
testcase_29 | AC | 379 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define rep(i,n) for(int i=0;i<(int)(n);i++) #define codefor int test;cin>>test;while(test--) #define INT(...) int __VA_ARGS__;in(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;in(__VA_ARGS__) #define vector2d(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__)) #define vector3d(type,name,h,w,...) vector<vector<vector<type>>>name(h,vector<vector<type>>(w,vector<type>(__VA_ARGS__))) using namespace std; using ll = long long; template<class T> using rpriority_queue = priority_queue<T, vector<T>, greater<T>>; template<class T> istream& operator>>(istream& is, vector<T>& vec) {for(T& x : vec)is >> x;return is;} template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) {if(vec.empty())return os;os << vec[0];for(auto it = vec.begin(); ++it!= vec.end();)os << ' ' << *it;return os;} void in(){} template <class Head, class... Tail> void in(Head& head, Tail&... tail){cin >> head;in(tail...);} void out(){cout << '\n';} template<class T>void out(const T& a){cout << a << '\n';} template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){cout << head << ' ';out(tail...);} const int INF = 1 << 30; const long long INF2 = 1ll << 60; template<class T> void chmax(T &a,const T b){if(b>a)a=b;} template<class T> void chmin(T &a,const T b){if(b<a)a=b;} struct dsu { public: int csz; dsu() : _n(0) {} dsu(int n) : _n(n), csz(n), parent_or_size(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); csz--; parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } std::vector<std::vector<int>> groups() { std::vector<int> leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector<std::vector<int>> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }), result.end()); return result; } private: int _n; // root node: -1 * component size // otherwise: parent std::vector<int> parent_or_size; }; template<typename T> T MUL(T a, T b){ T res; return __builtin_mul_overflow(a, b, &res)? std::numeric_limits<T>::max() : res; } int main(){ ios::sync_with_stdio(false); cin.tie(0); INT(n); vector<tuple<ll,ll,ll>> a(n); ll x, y, t, x1, y1, t1; for(int i = 0; i < n; i++){ cin >> x >> y >> t; a[i] = make_tuple(x, y, t); } auto sq = [&](ll v){ ll res = sqrt(v); for(int i = 5; i >= -5; i--){ if(4 * res * res + 4 * res * i + i * i <= 4 * v)return 2 * res + i; } return res; }; auto g = [&](ll s, ll x, ll y, ll x1, ll y1){ ll c1 = x * x + y * y, c2 = x1 * x1 + y1 * y1; ll c = s - (c1 + c2); if(c1 == c2) return true; if(c1 + c2 - sq(c1 * c2) <= s)return true; return false; }; auto f = [&](ll s){ dsu uf(n); for(int i = 0; i < n; i++){ tie(x, y, t) = a[i]; for(int j = i + 1; j < n; j++){ tie(x1, y1, t1) = a[j]; if(t != t1){ if(g(s, x, y, x1, y1))uf.merge(i, j); }else{ ll dx = x - x1, dy = y - y1; if(dx * dx + dy * dy <= s)uf.merge(i, j); } } } return uf.same(0, n - 1); }; ll ng = -1, ok = 1ll << 60, mid; while(ng + 1 < ok){ mid = (ng + ok) / 2; if(f(mid))ok = mid; else ng = mid; } out(ok); }