結果

問題 No.5007 Steiner Space Travel
ユーザー BinomialSheepBinomialSheep
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
//
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0