結果
| 問題 | No.5023 Airlines Optimization |
| コンテスト | |
| ユーザー |
 square1001
|
| 提出日時 | 2026-02-25 18:45:58 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 951 ms / 1,000 ms |
| コード長 | 11,281 bytes |
| 記録 | |
| コンパイル時間 | 3,087 ms |
| コンパイル使用メモリ | 169,496 KB |
| 実行使用メモリ | 7,848 KB |
| スコア | 50,727,621 |
| 最終ジャッジ日時 | 2026-02-25 20:51:05 |
| 合計ジャッジ時間 | 97,080 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#include <array>
#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);
}
class bit192 {
private:
array<uint64_t, 3> bit;
public:
int get(int idx) const {
return (bit[idx >> 6] >> (idx & 63)) & 1;
}
void set(int idx) {
bit[idx >> 6] |= uint64_t(1) << (idx & 63);
}
void unset(int idx) {
bit[idx >> 6] &= ~(uint64_t(1) << (idx & 63));
}
int query_one(int idx) const {
// find the last 1 in positions 0, ..., idx (inclusive!)
if (idx >= 128) {
uint64_t q = bit[2] & ((uint64_t(2) << (idx - 128)) - 1);
if (q) {
return 128 + (63 - __builtin_clzll(q));
}
}
if (idx >= 64) {
uint64_t q = bit[1] & ((uint64_t(2) << min(idx - 64, 63)) - 1);
if (q) {
return 64 + (63 - __builtin_clzll(q));
}
}
if (idx >= 0) {
uint64_t q = bit[0] & ((uint64_t(2) << min(idx, 63)) - 1);
if (q) {
return 63 - __builtin_clzll(q);
}
}
return -1;
}
};
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 hub = hub_opt.second;
cerr << "hub = " << hub << endl;
vector<int> c(N);
for (int i = 0; i < N; i++) {
c[i] = cost[hub][i];
}
// step #3. data structure for intervals
vector<bit192> state(N);
vector<vector<vector<int>>> ci_time(21, vector<vector<int>>(N, vector<int>(N, -1)));
ll score = 0;
auto update = [&](int t, int x, int y) -> void {
// update ci_time[t][x][y]
int s0 = t * 6 + 60, res = -1;
if (x != hub && y != hub) {
int s1 = state[x].query_one(s0);
int s2 = state[y].query_one(s1 - c[x] - c[y]);
res = s2;
}
if (x != hub && y == hub) {
int s1 = state[x].query_one(s0);
res = (s1 != -1 ? s1 - c[x] : -1);
}
if (x == hub && y != hub) {
int s2 = state[y].query_one(s0 - c[y]);
res = s2;
}
ll delta = (ll)(cities[x].w) * cities[y].w;
if (ci_time[t][x][y] > sq_time[t][x][y]) {
score -= delta;
}
ci_time[t][x][y] = res;
if (ci_time[t][x][y] > sq_time[t][x][y]) {
score += delta;
}
};
auto add = [&](int x, int y) -> void {
// (hub at time y-c[x]) --> (city x at time y) --> (hub at time y+c[x])
state[x].set(y);
for (int i = 0; i < 21; i++) {
for (int j = 0; j < N; j++) {
if (far[x][j]) {
update(i, x, j);
update(i, j, x);
}
}
}
};
auto remove = [&](int x, int y) -> void {
// (hub at time y-c[x]) --> (city x at time y) --> (hub at time y+c[x])
state[x].unset(y);
for (int i = 0; i < 21; i++) {
for (int j = 0; j < N; j++) {
if (far[x][j]) {
update(i, x, j);
update(i, j, x);
}
}
}
};
// step #4. hill climbing
const double TIME_LIMIT = 0.85;
const clock_t start_time = clock();
vector<pair<int, int>> place;
vector<int> span(180);
ll loops = 0;
while (true) {
loops++;
if ((loops & 7) == 0) {
clock_t cur_time = clock();
if (double(cur_time - start_time) / CLOCKS_PER_SEC >= TIME_LIMIT) {
break;
}
}
vector<pair<int, int>> old_place = place;
vector<int> old_span = span;
ll old_score = score;
int x, y;
do {
x = mt() % N;
y = mt() % 181;
} while (x == hub || state[x].get(y));
int l = max(y - c[x], 0);
int r = min(y + c[x], 180);
vector<int> c1_buf(r - l);
vector<int> c2_buf(place.size());
vector<pair<int, int>> erased;
while (true) {
int h = *max_element(span.begin() + l, span.begin() + r);
if (h < K) {
break;
}
int c1 = 0;
for (int i = l; i < r; i++) {
if (span[i] == K) {
c1_buf[c1++] = i;
}
}
int pos1 = c1_buf[mt() % c1];
int c2 = 0;
for (int i = 0; i < int(place.size()); i++) {
auto [sx, sy] = place[i];
if (sy - c[sx] <= pos1 && pos1 < sy + c[sx]) {
c2_buf[c2++] = i;
}
}
int pos2 = c2_buf[mt() % c2];
auto [tx, ty] = place[pos2];
for (int i = max(ty - c[tx], 0); i < min(ty + c[tx], 180); i++) {
span[i]--;
}
erased.push_back(place[pos2]);
place.erase(place.begin() + pos2);
remove(tx, ty);
}
place.emplace_back(x, y);
for (int i = l; i < r; i++) {
span[i]++;
}
add(x, y);
if (old_score <= score) {
if (old_score < score) {
cerr << "#" << loops << ": " << score << endl;
}
} else {
remove(x, y);
for (auto [sx, sy] : erased) {
add(sx, sy);
}
place = old_place;
span = old_span;
}
}
// step #4. greedy algorithm
vector<route> ans;
for (auto [x, y] : place) {
ans.push_back(route(hub, y - c[x], x, y));
ans.push_back(route(x, y, hub, y + c[x]));
}
const int MAX_TIME = 38;
const int Z = ans.size() / 2;
vector<bool> occupied(K);
vector<int> seat(Z, -1);
vector<vector<int>> g_start(181 + MAX_TIME * 2), g_end(181 + MAX_TIME * 2);
vector<vector<route>> final_ans(K);
for (int i = 0; i < Z; i++) {
g_start[ans[i * 2 + 0].s + MAX_TIME].push_back(i);
g_end[ans[i * 2 + 1].t + MAX_TIME].push_back(i);
}
for (int i = 0; i <= 180 + MAX_TIME * 2; i++) {
for (int j : g_end[i]) {
occupied[seat[j]] = false;
}
for (int j : g_start[i]) {
int x = -1;
for (int k = 0; k < K; k++) {
if (!occupied[k]) {
x = k;
break;
}
}
assert(x != -1);
occupied[x] = true;
seat[j] = x;
if (ans[j * 2 + 0].s >= 0) {
final_ans[x].push_back(ans[j * 2 + 0]);
}
if (ans[j * 2 + 1].t <= 180) {
final_ans[x].push_back(ans[j * 2 + 1]);
}
}
}
return final_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;
}