結果
問題 | No.2179 Planet Traveler |
ユーザー |
|
提出日時 | 2023-01-06 22:38:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 254 ms / 3,000 ms |
コード長 | 6,111 bytes |
コンパイル時間 | 1,935 ms |
コンパイル使用メモリ | 209,128 KB |
最終ジャッジ日時 | 2025-02-10 00:11:54 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#ifndef hari64#include <bits/stdc++.h>// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#define debug(...)#else#include "viewer.hpp"#define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__)#endif // clang-format offusing namespace std;constexpr int INF=1001001001;constexpr long long INFll=1001001001001001001;template<class T>bool chmax(T&a,const T&b){return a<b?a=b,1:0;}template<class T>bool chmin(T&a,const T&b){return a>b?a=b,1:0;} // clang-format on// clang-format off// Implement (union by size) + (path compression)// Reference: Zvi Galil and Giuseppe F. Italiano,struct UnionFind {explicit UnionFind(int n):_n(n),group_cnt(n),par_or_sz(n,-1),edge(n,0){}// the leader of the connected componentvirtual int merge(int a,int b){assert(0<=a&&a<_n&&0<=b&&b<_n);int x=find(a),y=find(b);if(x==y){edge[x]++;return x;};group_cnt--;if(-par_or_sz[x]<-par_or_sz[y])swap(x,y);edge[x]+=edge[y]+1;par_or_sz[x]+=par_or_sz[y];return par_or_sz[y]=x;}// the size of the connected component that contains the vertex avirtual int find(int a){assert(0<=a&&a<_n);return par_or_sz[a]<0?a:par_or_sz[a]=find(par_or_sz[a]);}// is samebool same(int a,int b){assert(0<=a&&a<_n&&0<=b&&b<_n);return find(a)==find(b);}// the size of the connected component that contains the vertex aint size(int a){assert(0<=a&&a<_n);return -par_or_sz[find(a)];}// cycle ⇒ -sz[a] <= -sz[a] - 1 = edge[a] (O(1)) / if a==-1 then check all vertexes (O(N))bool has_cycle(int a=-1){assert(-1<=a&&a<_n);if(0<=a){a=find(a);return -par_or_sz[a]<=edge[a];}else{for(int b=0;b<_n;b++)if(par_or_sz[b]<0&&-par_or_sz[b]<=edge[b])return true;}return false;}// tree ⇒ -sz[a] > -sz[a] - 1 = edge[a] O(N)int num_of_tree(){int num_of_tree=0;for(int a=0;a<_n;a++)if(par_or_sz[a]<0&&-par_or_sz[a]>edge[a])num_of_tree++;return num_of_tree;}// the list of the "list of the vertices in a connected component" O(N)vector<vector<int>>groups(bool index1=false){vector<vector<int>>ret(_n);for(int i=0;i<_n;i++)ret[find(i)].push_back(i+int(index1));ret.erase(remove_if(ret.begin(),ret.end(),[&](const vector<int>&v){return v.empty();}),ret.end());return ret;}// UnionFind::groups().size() O(1)int group_count(){return group_cnt;}protected:int _n;int group_cnt;/* root node: -1 * component size , otherwise: parent */vector<int>par_or_sz;vector<int>edge;};/// @ref https://qiita.com/drken/items/cce6fc5c579051e64fab/// @brief merge(a,b,w): A[a] - A[b] == z/// diff(a,b): A[b]-A[a] (REQUIRE:same(a,b))template <class Abel> struct weighted_dsu : UnionFind {explicit weighted_dsu(int n,Abel SUM_UNITY=0):diff_weight(n,SUM_UNITY){_n=n;group_cnt=0;par_or_sz.resize(n,-1);}int find(int a)override{assert(0<=a&&a<_n);if(par_or_sz[a]<0)return a;int r=find(par_or_sz[a]);diff_weight[a]+=diff_weight[par_or_sz[a]];returnpar_or_sz[a]=r;}int merge(int a,int b,Abel w){assert(0<=a&&a<_n&&0<=b&&b<_n);w+=weight(a)-weight(b);int x=find(a),y=find(b);if(x==y)return x;group_cnt--;if(-par_or_sz[x]<-par_or_sz[y])swap(x,y),w=-w;par_or_sz[x]+=par_or_sz[y];diff_weight[y]=w;return par_or_sz[y]=x;}Abel weight(int a){find(a);return diff_weight[a];}Abel diff(int a, int b){assert(same(a,b));return weight(b)-weight(a);}private:vector<Abel> diff_weight;};/// @ref https://misteer.hatenablog.com/entry/persistentUF/// @ref https://ei1333.github.io/library/structure/union-find/partially-persistent-union-find.cpp/// @brief UnionFind which can reference all previous versions and update the current (not previous) version./// @note t = -1 is the initial time.(each node's parent is itself)struct partially_persistent_dsu {partially_persistent_dsu(int n):_n(n),par_or_sz(n,-1),last(n,INF),add(n,{{-1,-1}}){}int merge(int a,int b,int t){assert(0<=a&&a<_n&&0<=b&&b<_n);int x=find(a,t),y=find(b,t);if(x==y)return x;if(-par_or_sz[x]<-par_or_sz[y])swap(x,y);last[y]=t;par_or_sz[x]+=par_or_sz[y];add[x].emplace_back(t,par_or_sz[x]);return par_or_sz[y]=x;}int find(int a,int t){assert(0<=a&&a<_n);if(t<last[a])return a;return find(par_or_sz[a],t);}bool same(int a,int b,int t){assert(0<=a&&a<_n&&0<=b&&b<_n);return find(a,t)==find(b,t);}int size(int a,int t){assert(0<=a&&a<_n);int x=find(a,t);return -prev(lower_bound(add[x].begin(),add[x].end(),make_pair(t,0)))->second;}private:int _n;vector<int>par_or_sz;vector<int>last;vector<vector<pair<int,int>>>add;};// clang-format onint main() {cin.tie(0);ios::sync_with_stdio(false);int N;cin >> N;vector<tuple<long long, long long, long long>> XYTs(N);for (int i = 0; i < N; i++) {long long X;long long Y;long long T;cin >> X >> Y >> T;XYTs[i] = make_tuple(X, Y, T);}auto is_ok = [&](long long s) -> bool {UnionFind uf(N);for (int i = 0; i < N; i++) {auto [xi, yi, ti] = XYTs[i];for (int j = 0; j < N; j++) {auto [xj, yj, tj] = XYTs[j];if (i == j) continue;if (xi * xi + yi * yi > xj * xj + yj * yj) continue;debug(i, j);if (ti == tj) {if ((xj - xi) * (xj - xi) + (yj - yi) * (yj - yi) <= s) {uf.merge(i, j);}} else {long long a = xi * xi + yi * yi + xj * xj + yj * yj - s;long long b =4ll * (xi * xi + yi * yi) * (xj * xj + yj * yj);if (a <= 0 || a * a <= b) {uf.merge(i, j);}}}}debug(s);debug(uf.groups());return uf.same(0, N - 1);};long long ok, ng;ok = INFll;ng = -1;while (abs(ok - ng) > 1) {long long mid = (ok + ng) / 2;if (is_ok(mid)) {ok = mid;} else {ng = mid;}}cout << ok << endl;return 0;}