結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 Pechi
|
| 提出日時 | 2026-02-25 22:25:21 |
| 言語 | C++17(clang) (clang++ 21.1.8 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 941 ms / 1,000 ms |
| コード長 | 6,537 bytes |
| 記録 | |
| コンパイル時間 | 5,483 ms |
| コンパイル使用メモリ | 197,056 KB |
| 実行使用メモリ | 17,296 KB |
| スコア | 30,763,168 |
| 最終ジャッジ日時 | 2026-02-25 22:27:13 |
| 合計ジャッジ時間 | 99,522 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#define _USE_MATH_DEFINES
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
#ifdef _MSC_VER
inline unsigned long long __builtin_ctzll(unsigned long long x) { unsigned long r; _BitScanForward64(&r, x); return r; }
inline unsigned long long __builtin_clzll(unsigned long long x) { unsigned long r; _BitScanReverse64(&r, x); return 63 - r; }
inline unsigned long long __builtin_ffsll(unsigned long long x) { unsigned long r; return _BitScanForward64(&r, x) ? r + 1 : 0; }
inline unsigned long long __builtin_popcountll(unsigned long long x) { return __popcnt64(x); }
#endif // _MSC_VER
#define LP(I,S,G) for (long long int I = (S); I < (G); ++I)
#define IN(X) for (int in = 0; in < X.size(); in++)cin >> X[in]
#define OUT(X) for (int in = 0; in < X.size(); in++)cout << X[in]<<" "
#define SORT(X) sort((X).begin(), (X).end())
#define CSORT(X,Y) sort(X.begin(), X.end(),Y)
#define COPY(X,Y) copy(X.begin(), X.end(), Y.begin())
#define ALL(X,Y) for (auto (X) :(Y))
#define FULL(a) (a).begin(),(a).end()
#define BFS(Q,S) for(Q.push(S);Q.size()!=0;Q.pop())
typedef long long int ll;
typedef unsigned long long int ull;
long long int M = 998244353;
chrono::system_clock::time_point starttime;
using namespace std::chrono;
using namespace atcoder;
#ifndef ONLINE_JUDGE
#define DEBUG
#endif
inline float getTime() {
#ifdef DEBUG
return duration_cast<milliseconds>(system_clock::now() - starttime).count() / 2;
#else
return duration_cast<milliseconds>(system_clock::now() - starttime).count();
#endif
}
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
inline long long int xor128() {
static long long int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
long long int t = (x ^ (x << 11));
x = y; y = z; z = w;
return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
mt19937_64 rnd;
struct Solver {
int n, r, m, k;
int plan_size = 16;
vector<ll> x, y, w;
vector<vector<array<int, 3>>> g;
vector<vector<int>> dist;
vector<vector<array<int, 4>>> plan;
string convert(int t) {
string a = to_string(t / 12 + 6);
if (a.size() == 1)a = "0" + a;
string b = to_string((t % 12) * 5);
if (b.size() == 1)b = "0" + b;
return a + ":" + b;
}
int convert(string s) {
int a = stoi(string(s.begin(), s.begin() + 2)) - 6;
int b = stoi(string(s.begin() + 3, s.end())) / 5;
return a * 12 + b;
}
void init_dist() {
dist = vector<vector<int>>(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
double d = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
dist[i][j] = ((int)ceil(3 * d / 40 + 40) + 4) / 5;
}
}
}
Solver() {
cin >> n >> r;
g = vector<vector<array<int, 3>>>(n);
x = vector<ll>(n);
y = vector<ll>(n);
w = vector<ll>(n);
for (int i = 0; i < n; ++i)cin >> x[i] >> y[i] >> w[i];
cin >> m;
for (int i = 0; i < m; ++i) {
int a, b;
string s, t;
cin >> a >> s >> b >> t;
--a, --b;
g[a].push_back({ b,convert(s),convert(t) });
}
cin >> k;
init_dist();
}
vector<array<int, 4>> make_plan(vector<int> target) {
shuffle(target.begin(), target.end(), rnd);
vector<vector<int>> dp((1 << target.size()), vector<int>(target.size(), INT_MAX)),p((1 << target.size()), vector<int>(target.size(), -1));
dp[1][0] = 0;
for (int b = 0; b < (1 << target.size()); ++b) {
bitset<20> bi(b);
for (int u = 0; u < target.size(); ++u) {
if (dp[b][u] == INT_MAX)continue;
for (int v = 0; v < target.size(); ++v) {
if (bi[v])continue;
int cost = dist[target[u]][target[v]];
if (dp[b + (1 << v)][v] > dp[b][u] + cost) {
dp[b + (1 << v)][v] = dp[b][u] + cost;
p[b + (1 << v)][v] = u;
}
}
}
}
vector<int> move;
int min_d = INT_MAX, now = 0;
for (int i = 0; i < target.size(); ++i) {
if (dp[(1 << target.size()) - 1][i] < min_d) {
min_d = dp[(1 << target.size()) - 1][i];
now = i;
}
}
int s = (1 << target.size()) - 1;
while (p[s][now] != -1) {
move.push_back(target[now]);
int next = p[s][now];
s -= (1 << now);
now = next;
}
move.push_back(target[now]);
now = 0;
vector<array<int, 4>> plan;
for (int i = 0; i < plan_size - 1; ++i) {
int next = now + dist[move[i]][move[i + 1]];
if (next > 180)break;
plan.push_back({ move[i],now,move[i + 1],next });
now = next;
}
for (int i = 0; i < plan.size(); ++i) {
plan[i][1] += 180 - now;
plan[i][3] += 180 - now;
}
return plan;
}
void solve() {
vector<array<ll, 2>> t(n);
for (int i = 0; i < n; ++i) {
t[i] = { w[i],i };
}
for (int i = 1; i < n; ++i)t[i][0] += t[i - 1][0];
vector<vector<int>> target;
set<vector<int>> ps;
while (target.size() < k) {
set<int> s;
while (s.size() != plan_size) {
int v = xor128() % (*t.rbegin())[0];
int idx = (*lower_bound(t.begin(), t.end(), array<ll,2>({ v,0 })))[1];
s.insert(idx);
}
vector<int> res = vector<int>(s.begin(), s.end());
if (ps.find(res) == ps.end()) {
ps.insert(res);
target.push_back(res);
}
}
for (int i = 0; i < target.size(); ++i) {
plan.push_back(make_plan(target[i]));
}
}
void answer() {
for (int i = 0; i < k; ++i) {
cout << plan[i].size() << "\n";
for (auto act : plan[i]) {
cout << act[0] + 1 << " " << convert(act[1]) << " " << act[2] + 1 << " " << convert(act[3]) << "\n";
}
}
}
};
int main(int argc, char* argv[]) {
starttime = chrono::system_clock::now();
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solver s;
s.solve();
s.answer();
exit(0);
}