#1149079 (C++17) No.5023 Airlines Optimization

提出ソース

結果

問題	No.5023 Airlines Optimization
コンテスト
ユーザー	square1001
提出日時	2026-02-22 18:09:17
言語	C++17 (gcc 15.2.0 + boost 1.89.0) コンパイル: `g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	TLE
実行時間	-
コード長	6,955 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	2,339 ms
コンパイル使用メモリ	155,520 KB
実行使用メモリ	7,976 KB
スコア	33,814,088
最終ジャッジ日時	2026-02-25 20:45:56
合計ジャッジ時間	93,592 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
other	AC * 89 TLE * 11

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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<vector<int>>> sq_time = calc_times(routes);

	// step #2. construction
	vector<int> sum_pop(N + 1);
	for (int i = 0; i < N; i++) {
		sum_pop[i + 1] = sum_pop[i] + cities[i].w;
	}
	auto rand_city = [&]() -> int {
		double z = double(mt()) / double(uint64_t(-1));
		int pos = lower_bound(sum_pop.begin(), sum_pop.end(), int(z * sum_pop[N])) - sum_pop.begin() - 1;
		return pos;
	};
	const int MAX_LOOPS = 300;
	vector<vector<route>> ans(K);
	int loops = 0;
	ll cur_ci_val = 0;
	while (loops < MAX_LOOPS) {
		loops++;
		int id = mt() % K;
		vector<route> pre_ans = ans[id];
		ans[id].clear();
		int start = rand_city();
		int t = 0, v = start;
		while (true) {
			vector<bool> possible(N);
			for (int j = 0; j < N; j++) {
				possible[j] = (t + cost[v][j] <= 180) && (v != j);
			}
			if (possible != vector<bool>(N, false)) {
				int nv = -1;
				do {
					nv = rand_city();
				} while (!possible[nv]);
				int nt = t + cost[v][nv];
				ans[id].push_back(route(v, t, nv, nt));
				v = nv;
				t = nt;
			} else {
				break;
			}
		}
		vector<vector<vector<int>>> ci_time = calc_times(flatten(ans));
		auto [sq_val, ci_val] = get_base_score(cities, sq_time, ci_time);
		if (cur_ci_val < ci_val) {
			double score = double(ci_val) / (sq_val + ci_val);
			cerr << "#" << loops << ": " << score << endl;
			cur_ci_val = ci_val;
		} else {
			ans[id] = pre_ans;
		}
	}

	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;
}

yukicoder

結果

ソースコード