結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
|
提出日時 | 2022-07-30 15:18:44 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 1,000 ms |
コード長 | 9,097 bytes |
コンパイル時間 | 2,791 ms |
実行使用メモリ | 3,860 KB |
スコア | 7,261,021 |
最終ジャッジ日時 | 2022-07-30 15:18:50 |
合計ジャッジ時間 | 4,479 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#pragma GCC optimize ("O3")#pragma GCC optimize ("unroll-loops")#pragma GCC target ("avx2")#include <iostream>#include <iomanip>#include <vector>#include <algorithm>#include <utility>#include <string>#include <queue>#include <stack>#include <unordered_set>#include <random>#include <cmath>#include <cassert>#include <x86intrin.h>struct xorshift64 {unsigned long long int x = 88172645463325252ULL;inline unsigned short nextUShort() {x = x ^ (x << 7);return x = x ^ (x >> 9);}inline unsigned int nextUShortMod(unsigned long long int mod) {x = x ^ (x << 7);x = x ^ (x >> 9);return ((x & 0x0000ffffffffffff) * mod) >> 48;}inline unsigned int nextUInt() {x = x ^ (x << 7);return x = x ^ (x >> 9);}inline unsigned int nextUIntMod(unsigned long long int mod) {x = x ^ (x << 7);x = x ^ (x >> 9);return ((x & 0x00000000ffffffff) * mod) >> 32;}inline unsigned long long int nextULL() {x = x ^ (x << 7);return x = x ^ (x >> 9);}inline double nextDouble() {x = x ^ (x << 7);x = x ^ (x >> 9);return (double)x * 5.42101086242752217e-20;}};struct timer {double t = 0.0;double lastStop = 0.0;bool stopped = false;timer() {restart();}inline void restart() {t = now();stopped = false;}inline void start() {if (stopped) {t += now() - lastStop;stopped = false;}}inline void stop() {if (!stopped) {lastStop = now();stopped = true;}}inline double time() {if (stopped) return lastStop - t;else return now() - t;}inline double now() {unsigned long long l, h;__asm__ ("rdtsc" : "=a"(l), "=d"(h));#ifdef LOCALreturn (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X)#else//return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2)//return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3)return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL)#endif}};using namespace std;typedef long long int ll;typedef unsigned long long int ull;typedef pair<int, int> Pii;const ll mod = 1000000007;timer theTimer;xorshift64 theRandom;mt19937 theMersenne(1);// hyper parameters// enums// structs// constantsconstexpr int planet_num = 100;constexpr int station_num = 8;constexpr int planet_cost_factor = 5;// inputsvector<Pii> planet_pos;// outputsvector<Pii> station_pos;vector<Pii> route_info;// internalsvector<vector<int> > planet_to_planet_cost;vector<vector<int> > station_to_planet_cost;vector<vector<int> > station_to_station_cost;vector<int> planet_visit_order;void receive_input() {int _n, _m;cin >> _n >> _m;planet_pos = vector<Pii>(planet_num);for (auto &planet: planet_pos) cin >> planet.first >> planet.second;}void init_planet_to_planet_cost() {planet_to_planet_cost = vector<vector<int> >(planet_num, vector<int>(planet_num));for (int i = 0; i < planet_num; i++) {for (int j = i; j < planet_num; j++) {planet_to_planet_cost[i][j] = planet_cost_factor * planet_cost_factor * ((planet_pos[i].first - planet_pos[j].first) * (planet_pos[i].first -planet_pos[j].first) + (planet_pos[i].second - planet_pos[j].second) * (planet_pos[i].second - planet_pos[j].second));planet_to_planet_cost[j][i] = planet_to_planet_cost[i][j];}}}void init_station_to_planet_cost() {station_to_planet_cost = vector<vector<int> >(station_num, vector<int>(planet_num));for (int i = 0; i < station_num; i++) {for (int j = 0; j < planet_num; j++) {station_to_planet_cost[i][j] = planet_cost_factor * ((station_pos[i].first - planet_pos[j].first) * (station_pos[i].first - planet_pos[j].first) + (station_pos[i].second - planet_pos[j].second) * (station_pos[i].second - planet_pos[j].second));}}}void init_station_to_station_cost() {station_to_station_cost = vector<vector<int> >(station_num, vector<int>(planet_num));for (int i = 0; i < station_num; i++) {for (int j = i; j < station_num; j++) {station_to_station_cost[i][j] = ((station_pos[i].first - station_pos[j].first) * (station_pos[i].first - station_pos[j].first) +(station_pos[i].second - station_pos[j].second) * (station_pos[i].second - station_pos[j].second));}}}void init() {station_pos = vector<Pii>(station_num);for (int i = 0; i < station_num; i++) {station_pos[i] = Pii(theRandom.nextUIntMod(801) + 100, theRandom.nextUIntMod(801) + 100);}init_planet_to_planet_cost();init_station_to_planet_cost();init_station_to_station_cost();planet_visit_order = vector<int>(planet_num + 1);{planet_visit_order[0] = 0;planet_visit_order[planet_num] = 0;int current_planet = 0;vector<bool> visited(planet_num);visited[0] = true;for (int i = 1; i < planet_num; i++) {int best_planet = -1;int best_cost = 1000000007;for (int j = 0; j < planet_num; j++) {if (!visited[j] && planet_to_planet_cost[current_planet][j] < best_cost) {best_planet = j;best_cost = planet_to_planet_cost[current_planet][j];}}planet_visit_order[i] = best_planet;current_planet = best_planet;visited[best_planet] = true;}}}vector<Pii> find_shortest_route(int planet_from, int planet_to) {vector<bool> planet_visited(planet_num);vector<bool> station_visited(station_num);vector<Pii> planet_prev_entity(planet_num);vector<Pii> station_prev_entity(station_num);priority_queue<tuple<int, int, int, int, int>, vector<tuple<int, int, int, int, int> >, greater<tuple<int, int, int, int, int> > > que; // cost,entity_type, entity_id, prev_entity_type, prev_entity_idque.emplace(0, 1, planet_from, 1, planet_from);while (!que.empty()) {auto [cost, entity_type, entity_id, prev_entity_type, prev_entity_id] = que.top();que.pop();if (entity_type == 1) { // planetif (planet_visited[entity_id]) continue;planet_visited[entity_id] = true;planet_prev_entity[entity_id] = Pii(prev_entity_type, prev_entity_id);if (entity_id == planet_to) break;for (int next_planet = 0; next_planet < planet_num; next_planet++) {if (!planet_visited[next_planet]) {que.emplace(cost + planet_to_planet_cost[entity_id][next_planet], 1, next_planet, entity_type, entity_id);}}for (int next_station = 0; next_station < station_num; next_station++) {if (!station_visited[next_station]) {que.emplace(cost + station_to_planet_cost[next_station][entity_id], 2, next_station, entity_type, entity_id);}}}else if (entity_type == 2) { // stationif (station_visited[entity_id]) continue;station_visited[entity_id] = true;station_prev_entity[entity_id] = Pii(prev_entity_type, prev_entity_id);for (int next_planet = 0; next_planet < planet_num; next_planet++) {if (!planet_visited[next_planet]) {que.emplace(cost + station_to_planet_cost[entity_id][next_planet], 1, next_planet, entity_type, entity_id);}}for (int next_station = 0; next_station < station_num; next_station++) {if (!station_visited[next_station]) {que.emplace(cost + station_to_station_cost[entity_id][next_station], 2, next_station, entity_type, entity_id);}}}}vector<Pii> route;int current_entity_type = 1;int current_entity_id = planet_to;while (!(current_entity_type == 1 && current_entity_id == planet_from)) {route.emplace_back(current_entity_type, current_entity_id);if (current_entity_type == 1) { // planetauto [prev_entity_type, prev_entity_id] = planet_prev_entity[current_entity_id];current_entity_type = prev_entity_type;current_entity_id = prev_entity_id;}else if (current_entity_type == 2) { // stationauto [prev_entity_type, prev_entity_id] = station_prev_entity[current_entity_id];current_entity_type = prev_entity_type;current_entity_id = prev_entity_id;}}reverse(route.begin(), route.end());return route;}void update_route_info() {route_info.emplace_back(1, 0);for (int i = 0; i < planet_num; i++) {auto path = find_shortest_route(planet_visit_order[i], planet_visit_order[i + 1]);for (auto &entity: path) route_info.push_back(entity);}}void solve() {update_route_info();}void output_ans() {for (auto &station: station_pos) {cout << station.first << " " << station.second << endl;}cout << route_info.size() << endl;for (auto &route: route_info) {cout << route.first << " " << route.second + 1 << endl;}}int main(int argc, char *argv[]) {cin.tie(0);ios::sync_with_stdio(false);receive_input();init();solve();output_ans();return 0;}