結果
問題 | No.5007 Steiner Space Travel |
ユーザー | BinomialSheep |
提出日時 | 2022-07-31 16:54:11 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 4 ms / 1,000 ms |
コード長 | 3,489 bytes |
コンパイル時間 | 2,149 ms |
実行使用メモリ | 6,952 KB |
スコア | 1,650,513 |
最終ジャッジ日時 | 2022-07-31 16:54:16 |
合計ジャッジ時間 | 4,093 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,948 KB |
testcase_01 | AC | 2 ms
4,900 KB |
testcase_02 | AC | 2 ms
4,900 KB |
testcase_03 | AC | 2 ms
4,900 KB |
testcase_04 | AC | 2 ms
4,900 KB |
testcase_05 | AC | 2 ms
4,900 KB |
testcase_06 | AC | 2 ms
4,900 KB |
testcase_07 | AC | 2 ms
4,900 KB |
testcase_08 | AC | 2 ms
4,900 KB |
testcase_09 | AC | 2 ms
4,904 KB |
testcase_10 | AC | 2 ms
4,904 KB |
testcase_11 | AC | 4 ms
4,904 KB |
testcase_12 | AC | 3 ms
6,952 KB |
testcase_13 | AC | 2 ms
6,952 KB |
testcase_14 | AC | 2 ms
4,900 KB |
testcase_15 | AC | 2 ms
4,904 KB |
testcase_16 | AC | 2 ms
4,904 KB |
testcase_17 | AC | 2 ms
4,900 KB |
testcase_18 | AC | 2 ms
6,948 KB |
testcase_19 | AC | 2 ms
4,900 KB |
testcase_20 | AC | 2 ms
4,904 KB |
testcase_21 | AC | 2 ms
4,900 KB |
testcase_22 | AC | 2 ms
4,900 KB |
testcase_23 | AC | 2 ms
4,904 KB |
testcase_24 | AC | 2 ms
4,904 KB |
testcase_25 | AC | 2 ms
4,904 KB |
testcase_26 | AC | 2 ms
4,904 KB |
testcase_27 | AC | 2 ms
4,900 KB |
testcase_28 | AC | 2 ms
4,900 KB |
testcase_29 | AC | 3 ms
6,948 KB |
ソースコード
#include <bits/stdc++.h> // デバッグ用マクロ:https://naskya.net/post/0002/ #ifdef LOCAL #include <debug_print.hpp> #define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (static_cast<void>(0)) #endif using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<long long>; using vs = vector<string>; using vc = vector<char>; using vb = vector<bool>; using vpii = vector<pair<int, int>>; using vpll = vector<pair<long long, long long>>; using vvi = vector<vector<int>>; using vvl = vector<vector<long long>>; using vvc = vector<vector<char>>; using vvb = vector<vector<bool>>; using vvvi = vector<vector<vector<int>>>; using pii = pair<int, int>; // #include <atcoder/all> // using namespace atcoder; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define all(x) (x).begin(), (x).end() // #define MAX 10000 #define INFTY (1 << 30) // 浮動小数点の誤差を考慮した等式 #define EPS (1e-10) #define equal(a, b) (fabs((a) - (b)) < EPS) template <typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template <typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } struct Solver { int N, M; vi a, b; // α int A = 5; vpii stupidInit() { vpii ret; rep(i, N) ret.emplace_back(1, i + 1); ret.emplace_back(1, 1); return ret; } vpii greedyInit() { vpii ret; vector<vpii> distList(N); auto dist = [](int x1, int y1, int x2, int y2) { return (ll)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }; rep(i, N) rep(j, i) { int x1 = a[i]; int y1 = b[i]; int x2 = a[j]; int y2 = b[j]; auto d = A * A * dist(x1, y1, x2, y2); distList[i].emplace_back(d, j); distList[j].emplace_back(d, i); } rep(i, N) sort(all(distList[i])); vi color(N); int now = 0; color[0] = 1; ret.emplace_back(1, 1); rep(i, N) { for (auto p : distList[now]) { if (color[p.second]) continue; now = p.second; color[p.second] = 1; ret.emplace_back(1, now + 1); } } ret.emplace_back(1, 1); return ret; } // シンプルなスコア計算 ll calcScore(vpii &tr) { ll ret = 0; int len = (int)tr.size(); auto dist = [](int x1, int y1, int x2, int y2) { return (ll)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }; rep(i, len - 1) { if (tr[i].first == 1 && tr[i + 1].first == 1) { int x1 = a[tr[i].second - 1]; int y1 = b[tr[i].second - 1]; int x2 = a[tr[i + 1].second - 1]; int y2 = b[tr[i + 1].second - 1]; ret += A * A * dist(x1, y1, x2, y2); } else if (tr[i].first == 2 && tr[i + 1].first == 2) { // TODO } else { // TODO } } return ret; } void solve() { /* input */ cin >> N >> M; a.resize(N); b.resize(N); rep(i, N) cin >> a[i] >> b[i]; /* solve */ vpii cd(M); // vpii tr = stupidInit(); vpii tr = greedyInit(); debug(calcScore(tr)); /* output */ int V = (int)tr.size(); assert(tr[0].second == 1); assert(tr[V - 1].second == 1); rep(i, M) cout << cd[i].first << " " << cd[i].second << "\n"; cout << V << endl; rep(i, V) cout << tr[i].first << " " << tr[i].second << "\n"; } }; int main() { int ts = 1; rep(ti, ts) { Solver solver; solver.solve(); } return 0; }