#830991 (C++17) No.2179 Planet Traveler

• 問題: No.2179 Planet Traveler
• ユーザー: hari64
• 提出日時: 2023-01-06 22:38:19
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 283 ms / 3,000 ms
• コード長: 6,111 bytes
• コンパイル時間: 2,664 ms
• コンパイル使用メモリ: 218,420 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-05-07 22:18:45
• 合計ジャッジ時間: 7,572 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	283 ms; 5,376 KB
testcase_12	AC	265 ms; 5,376 KB
testcase_13	AC	252 ms; 5,376 KB
testcase_14	AC	262 ms; 5,376 KB
testcase_15	AC	260 ms; 5,376 KB
testcase_16	AC	262 ms; 5,376 KB
testcase_17	AC	263 ms; 5,376 KB
testcase_18	AC	259 ms; 5,376 KB
testcase_19	AC	261 ms; 5,376 KB
testcase_20	AC	33 ms; 5,376 KB
testcase_21	AC	247 ms; 5,376 KB
testcase_22	AC	157 ms; 5,376 KB
testcase_23	AC	132 ms; 5,376 KB
testcase_24	AC	210 ms; 5,376 KB
testcase_25	AC	161 ms; 5,376 KB
testcase_26	AC	226 ms; 5,376 KB
testcase_27	AC	33 ms; 5,376 KB
testcase_28	AC	105 ms; 5,376 KB
testcase_29	AC	208 ms; 5,376 KB

ソースコード

#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;
}