結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 square1001
|
| 提出日時 | 2026-02-22 23:46:37 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 20 ms / 1,000 ms |
| コード長 | 9,084 bytes |
| 記録 | |
| コンパイル時間 | 2,910 ms |
| コンパイル使用メモリ | 170,604 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 38,738,864 |
| 最終ジャッジ日時 | 2026-02-25 20:45:52 |
| 合計ジャッジ時間 | 8,652 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <cmath>
#include <queue>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
mt19937_64 mt(1);
const int N = 47;
const int R = 1000;
const int M = 400;
const int K = 25;
int convert_time_int(string s) {
assert(s.size() == 5);
assert('0' <= s[0] && s[0] <= '9');
assert('0' <= s[1] && s[1] <= '9');
assert(s[2] == ':');
assert('0' <= s[3] && s[3] <= '9');
assert('0' <= s[4] && s[4] <= '9');
int h = int(s[0] - '0') * 10 + int(s[1] - '0');
int m = int(s[3] - '0') * 10 + int(s[4] - '0');
assert(make_pair(h, m) >= make_pair(6, 0));
assert(make_pair(h, m) <= make_pair(21, 0));
assert(m % 5 == 0);
return (h - 6) * 12 + (m / 5);
}
string convert_int_time(int x) {
assert(0 <= x && x <= 180);
int h = x / 12 + 6;
int m = (x % 12) * 5;
string res;
res += char(h / 10 + '0');
res += char(h % 10 + '0');
res += ':';
res += char(m / 10 + '0');
res += char(m % 10 + '0');
return res;
}
int sqr(int x) {
return x * x;
}
class city {
public:
int x, y, w;
explicit city() : x(0), y(0), w(0) {}
explicit city(int x_, int y_, int w_) : x(x_), y(y_), w(w_) {}
};
class route {
public:
int a, s, b, t;
explicit route() : a(-1), s(-1), b(-1), t(-1) {}
explicit route(int a_, int s_, int b_, int t_) : a(a_), s(s_), b(b_), t(t_) {}
};
int get_norm(const city& c1, const city& c2) {
return sqr(c2.x - c1.x) + sqr(c2.y - c1.y);
}
int req_time(const city& c1, const city& c2) {
int norm = get_norm(c1, c2);
int res = ceil((60 * sqrt(norm) / 800 + 40) / 5);
return res;
}
vector<vector<vector<int>>> calc_times(const vector<route>& routes) {
vector<vector<int>> base_g(N);
for (int i = 0; i < int(routes.size()); i++) {
base_g[routes[i].b].push_back(i);
}
vector<vector<vector<int>>> base_time(21, vector<vector<int>>(N));
for (int i = 0; i <= 20; i++) {
int start = i * 6 + 60;
for (int j = 0; j < N; j++) {
vector<int> d(N, -1);
d[j] = start;
priority_queue<pair<int, int>> que;
que.emplace(start, j);
while (!que.empty()) {
auto [t, u] = que.top();
que.pop();
if (d[u] == t) {
vector<int> best_s(N, -1);
for (int k : base_g[u]) {
const route& r = routes[k];
if (r.t <= t) {
best_s[r.a] = max(best_s[r.a], r.s);
}
}
for (int k = 0; k < N; k++) {
if (d[k] < best_s[k]) {
d[k] = best_s[k];
que.emplace(d[k], k);
}
}
}
}
base_time[i][j] = d;
}
}
return base_time;
}
vector<route> flatten(const vector<vector<route>>& ans) {
vector<route> res;
for (const vector<route>& v : ans) {
for (const route& r : v) {
res.push_back(r);
}
}
return res;
}
pair<ll, ll> get_base_score(const vector<city>& cities, const vector<vector<vector<int>>>& sq_time, const vector<vector<vector<int>>>& ci_time) {
ll sq_val = 0;
ll ci_val = 0;
for (int i = 0; i < 21; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
int norm = get_norm(cities[j], cities[k]);
if (norm * 16 >= R * R) {
if (ci_time[i][j][k] > sq_time[i][j][k]) {
ci_val += (ll)(cities[j].w) * cities[k].w;
} else {
sq_val += (ll)(cities[j].w) * cities[k].w;
}
}
}
}
}
return make_pair(sq_val, ci_val);
}
vector<vector<route>> solve(const vector<city>& cities, const vector<route>& routes) {
// step #1. calculate distances
vector<vector<int>> cost(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i != j) {
cost[i][j] = req_time(cities[i], cities[j]);
}
}
}
vector<vector<bool>> far(N, vector<bool>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
far[i][j] = (get_norm(cities[i], cities[j]) * 16 >= R * R);
}
}
vector<vector<vector<int>>> sq_time = calc_times(routes);
// step #2. find optimal hub
pair<ll, int> hub_opt = make_pair(7LL << 58, -1);
for (int i = 0; i < N; i++) {
ll total = 0;
for (int j = 0; j < N; j++) {
for (int k = j + 1; k < N; k++) {
if (far[j][k]) {
int d = cost[j][i] + cost[k][i];
total += (ll)(d) * cities[j].w * cities[k].w;
}
}
}
hub_opt = min(hub_opt, make_pair(total, i));
}
int start = hub_opt.second;
cerr << "hub = " << start << endl;
// step #3. greedy algorithm
auto conv = [&](int t) -> int {
return (max(t - 60, 0) + 4) / 5;
};
vector<vector<route>> ans(K);
vector<int> cur_time(K, 180);
vector<int> last_reach(N, 21);
priority_queue<tuple<int, int, int>> updates;
vector<vector<vector<bool>>> win(21, vector<vector<bool>>(N, vector<bool>(N, false)));
for (int i = 0; i < K; i++) {
int id = i + int(i >= start);
ans[i].push_back(route(start, 180 - cost[id][start], id, 180));
cur_time[i] = 180 - cost[id][start];
last_reach[id] = 20;
}
ll delta_sum = 0;
while (true) {
int id = max_element(cur_time.begin(), cur_time.end()) - cur_time.begin();
while (!updates.empty() && get<0>(updates.top()) >= cur_time[id]) {
auto [st, spos, sval] = updates.top();
updates.pop();
last_reach[spos] = min(last_reach[spos], sval);
}
pair<ll, int> best = make_pair(ll(-1), -1);
for (int j = 0; j < N; j++) {
if (j != start) {
int t = cur_time[id] - 2 * cost[j][start];
if (t >= 0) {
int pt = cur_time[id] - cost[j][start];
ll delta = 0;
for (int k = 0; k < N; k++) {
if (k != start && far[j][k]) {
for (int l = last_reach[k]; l <= 20; l++) {
if (!win[l][j][k] && pt > sq_time[l][j][k]) {
delta += (ll)(cities[j].w) * cities[k].w;
}
}
}
}
for (int k = conv(cur_time[id]); k <= 20; k++) {
if (!win[k][start][j] && pt > sq_time[k][start][j]) {
delta += (ll)(cities[j].w) * cities[start].w;
}
}
for (int k = conv(pt); k <= 20; k++) {
if (!win[k][j][start] && t > sq_time[k][j][start]) {
delta += (ll)(cities[j].w) * cities[start].w;
}
}
best = max(best, make_pair(delta, j));
}
}
}
cerr << best.first << " " << best.second << endl;
int pos = best.second;
if (pos == -1) {
break;
}
int pos_time = cur_time[id] - 2 * cost[pos][start];
int pre_time = cur_time[id] - cost[pos][start];
for (int j = 0; j < N; j++) {
if (j != start && far[j][pos]) {
for (int k = last_reach[j]; k <= 20; k++) {
if (!win[k][pos][j] && pre_time > sq_time[k][pos][j]) {
win[k][pos][j] = true;
}
}
}
}
for (int j = conv(cur_time[id]); j <= 20; j++) {
if (!win[j][start][pos] && pre_time > sq_time[j][start][pos]) {
win[j][start][pos] = true;
}
}
for (int j = conv(pre_time); j <= 20; j++) {
if (!win[j][pos][start] && pos_time > sq_time[j][pos][start]) {
win[j][pos][start] = true;
}
}
ans[id].push_back(route(pos, pre_time, start, cur_time[id]));
ans[id].push_back(route(start, pos_time, pos, pre_time));
cur_time[id] = pos_time;
updates.emplace(pos_time, pos, conv(pre_time));
delta_sum += best.first;
}
for (int i = 0; i < K; i++) {
reverse(ans[i].begin(), ans[i].end());
}
cerr << "delta_sum = " << delta_sum << endl;
return ans;
}
void output_score(const vector<city>& cities, const vector<route>& routes, const vector<vector<route>>& ans) {
// step #1. check if the answer is valid
if (ans.size() != K) {
cerr << "wrong answer [1]" << endl;
return;
}
for (int i = 0; i < K; i++) {
int rs = ans[i].size();
for (int j = 0; j < rs; j++) {
route r = ans[i][j];
if (!(0 <= r.a && r.a < N && 0 <= r.b && r.b < N && 0 <= r.s && r.s <= 180 && 0 <= r.t && r.t <= 180)) {
cerr << "wrong answer [2]" << endl;
return;
}
if (r.t - r.s != req_time(cities[r.a], cities[r.b])) {
cerr << "wrong answer [3]" << endl;
return;
}
if (j >= 1) {
route pr = ans[i][j - 1];
if (!(pr.b == r.a && pr.t <= r.s)) {
cerr << "wrong answer [4]" << endl;
return;
}
}
}
}
// step #2. compute score
vector<vector<vector<int>>> sq_time = calc_times(routes);
vector<vector<vector<int>>> ci_time = calc_times(flatten(ans));
auto [sq_val, ci_val] = get_base_score(cities, sq_time, ci_time);
double share = double(ci_val) / (sq_val + ci_val);
cerr << "sq_val = " << sq_val << endl;
cerr << "ci_val = " << ci_val << endl;
cerr << "score = " << int(share * 1000000) << endl;
}
int main() {
int TMP_N, TMP_R, TMP_M, TMP_K;
cin >> TMP_N >> TMP_R;
vector<city> cities(N);
for (int i = 0; i < N; i++) {
cin >> cities[i].x >> cities[i].y >> cities[i].w;
}
cin >> TMP_M;
vector<route> routes(M);
for (int i = 0; i < M; i++) {
int a, b; string cs, ct;
cin >> a >> cs >> b >> ct;
routes[i].a = a - 1;
routes[i].s = convert_time_int(cs);
routes[i].b = b - 1;
routes[i].t = convert_time_int(ct);
}
vector<vector<route>> ans = solve(cities, routes);
for (int i = 0; i < K; i++) {
cout << ans[i].size() << endl;
for (const route& r : ans[i]) {
cout << r.a + 1 << ' ' << convert_int_time(r.s) << ' ' << r.b + 1 << ' ' << convert_int_time(r.t) << endl;
}
}
output_score(cities, routes, ans);
return 0;
}