結果
問題 | No.2179 Planet Traveler |
ユーザー |
![]() |
提出日時 | 2023-01-06 21:54:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 73 ms / 3,000 ms |
コード長 | 2,327 bytes |
コンパイル時間 | 1,240 ms |
コンパイル使用メモリ | 90,440 KB |
実行使用メモリ | 12,824 KB |
最終ジャッジ日時 | 2024-11-30 17:53:38 |
合計ジャッジ時間 | 3,147 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#ifndef CLASS_DISJOINT_SET #define CLASS_DISJOINT_SET #include <vector> #include <cstdint> #include <cstring> #include <algorithm> class disjoint_set { private: typedef std::int32_t value_type; std::vector<value_type> val; public: explicit disjoint_set() : val() {}; explicit disjoint_set(std::size_t n) : val(n, -1) {}; std::size_t size() const { return val.size(); } std::size_t size(std::size_t elem) { return std::size_t(-val[root(elem)]); } std::size_t root(std::size_t elem) { // path halving while (val[elem] >= 0 && val[val[elem]] >= 0) { val[elem] = val[val[elem]]; elem = val[elem]; } return std::size_t(val[elem] >= 0 ? val[elem] : elem); } void link(std::size_t elemx, std::size_t elemy) { elemx = root(elemx); elemy = root(elemy); if (elemx == elemy) return; if (val[elemx] > val[elemy]) { std::swap(elemx, elemy); } val[elemx] += val[elemy]; val[elemy] = elemx; } bool connected(std::size_t elemx, std::size_t elemy) { return root(elemx) == root(elemy); } }; #endif // CLASS_DISJOINT_SET #include <cmath> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { // step #1. input int N; cin >> N; vector<long long> X(N), Y(N), T(N); for (int i = 0; i < N; i++) { cin >> X[i] >> Y[i] >> T[i]; } // step #2. calculate distance vector<long double> radius(N); for (int i = 0; i < N; i++) { radius[i] = sqrtl(X[i] * X[i] + Y[i] * Y[i]); } auto sqr = [](long long x) { return x * x; }; vector<vector<long long> > d(N, vector<long long>(N)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { d[i][j] = (T[i] == T[j] ? sqr(X[i] - X[j]) + sqr(Y[i] - Y[j]) : ceil((radius[i] - radius[j]) * (radius[i] - radius[j]))); } } // step #3. main calculation vector<pair<int, int> > edges; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { edges.push_back(make_pair(i, j)); } } sort(edges.begin(), edges.end(), [&](const pair<int, int>& p1, const pair<int, int>& p2) { return d[p1.first][p1.second] < d[p2.first][p2.second]; }); disjoint_set uf(N); long long answer = -1; for (pair<int, int> i : edges) { uf.link(i.first, i.second); if (uf.connected(0, N - 1)) { answer = d[i.first][i.second]; break; } } // step #4. output cout << answer << endl; return 0; }