結果
| 問題 | No.2179 Planet Traveler |
| ユーザー |
 hari64
|
| 提出日時 | 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 off
using 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 component
virtual 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 a
virtual 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 same
bool 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 a
int 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]];return par_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 on
int 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;
}