結果
問題 | No.5007 Steiner Space Travel |
ユーザー | BinomialSheep |
提出日時 | 2022-07-31 16:16:44 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 2,677 bytes |
コンパイル時間 | 2,332 ms |
実行使用メモリ | 6,952 KB |
スコア | 1,221,702 |
最終ジャッジ日時 | 2022-07-31 16:16:48 |
合計ジャッジ時間 | 4,005 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,900 KB |
testcase_01 | AC | 1 ms
6,948 KB |
testcase_02 | AC | 2 ms
4,904 KB |
testcase_03 | AC | 1 ms
6,952 KB |
testcase_04 | AC | 1 ms
4,904 KB |
testcase_05 | AC | 2 ms
6,948 KB |
testcase_06 | AC | 1 ms
6,948 KB |
testcase_07 | AC | 1 ms
4,904 KB |
testcase_08 | AC | 1 ms
4,900 KB |
testcase_09 | AC | 1 ms
4,900 KB |
testcase_10 | AC | 2 ms
6,948 KB |
testcase_11 | AC | 1 ms
4,908 KB |
testcase_12 | AC | 1 ms
4,904 KB |
testcase_13 | AC | 2 ms
6,948 KB |
testcase_14 | AC | 2 ms
4,900 KB |
testcase_15 | AC | 1 ms
4,900 KB |
testcase_16 | AC | 1 ms
4,904 KB |
testcase_17 | AC | 2 ms
4,900 KB |
testcase_18 | AC | 1 ms
6,948 KB |
testcase_19 | AC | 1 ms
4,900 KB |
testcase_20 | AC | 2 ms
4,900 KB |
testcase_21 | AC | 1 ms
4,904 KB |
testcase_22 | AC | 1 ms
4,900 KB |
testcase_23 | AC | 2 ms
4,904 KB |
testcase_24 | AC | 1 ms
4,908 KB |
testcase_25 | AC | 2 ms
4,904 KB |
testcase_26 | AC | 2 ms
4,900 KB |
testcase_27 | AC | 2 ms
4,904 KB |
testcase_28 | AC | 1 ms
4,904 KB |
testcase_29 | AC | 2 ms
4,900 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))#endifusing 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;}// シンプルなスコア計算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();debug(tr);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;}