結果
問題 | 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 halvingwhile (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. inputint 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 distancevector<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 calculationvector<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. outputcout << answer << endl;return 0;}