#783009 (C++17) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	takumi152
提出日時	2022-07-30 15:37:35
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	10 ms / 1,000 ms
コード長	10,605 bytes
コンパイル時間	3,530 ms
実行使用メモリ	6,952 KB
スコア	7,903,009
最終ジャッジ日時	2022-07-30 15:37:40
合計ジャッジ時間	5,577 ms
ジャッジサーバーID （参考情報）	judge11 / judge14
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	9 ms 4,904 KB
testcase_01	AC	8 ms 4,904 KB
testcase_02	AC	9 ms 6,948 KB
testcase_03	AC	9 ms 6,952 KB
testcase_04	AC	8 ms 4,904 KB
testcase_05	AC	8 ms 4,908 KB
testcase_06	AC	9 ms 4,900 KB
testcase_07	AC	9 ms 4,900 KB
testcase_08	AC	9 ms 4,904 KB
testcase_09	AC	10 ms 6,948 KB
testcase_10	AC	9 ms 4,904 KB
testcase_11	AC	8 ms 6,948 KB
testcase_12	AC	9 ms 4,900 KB
testcase_13	AC	10 ms 6,952 KB
testcase_14	AC	8 ms 4,904 KB
testcase_15	AC	8 ms 4,900 KB
testcase_16	AC	9 ms 4,900 KB
testcase_17	AC	10 ms 6,948 KB
testcase_18	AC	10 ms 4,900 KB
testcase_19	AC	10 ms 4,904 KB
testcase_20	AC	9 ms 4,904 KB
testcase_21	AC	8 ms 4,904 KB
testcase_22	AC	8 ms 4,900 KB
testcase_23	AC	9 ms 4,904 KB
testcase_24	AC	9 ms 6,952 KB
testcase_25	AC	9 ms 4,900 KB
testcase_26	AC	8 ms 4,908 KB
testcase_27	AC	8 ms 4,900 KB
testcase_28	AC	9 ms 6,952 KB
testcase_29	AC	9 ms 6,952 KB

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

ソースコード

raw source code

#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 LOCAL
    return (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

// constants
constexpr int planet_num = 100;
constexpr int station_num = 8;

constexpr int planet_cost_factor = 5;

// inputs
vector<Pii> planet_pos;

// outputs
vector<Pii> station_pos;
vector<Pii> route_info;

// internals
vector<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);
  }
  {
    vector<int> planet_cluster(planet_num);
    for (int i = 0; i < planet_num; i++) planet_cluster[i] = theRandom.nextUIntMod(station_num);
    vector<int> next_planet_cluster = planet_cluster;
    int iter_count = 0;
    do {
      planet_cluster = next_planet_cluster;
      vector<int> cluster_count(station_num);
      vector<Pii> cluster_pos_sum(station_num);
      for (int i = 0; i < planet_num; i++) {
        cluster_count[planet_cluster[i]]++;
        cluster_pos_sum[planet_cluster[i]].first += planet_pos[i].first;
        cluster_pos_sum[planet_cluster[i]].second += planet_pos[i].second;
      }
      for (int i = 0; i < station_num; i++) {
        if (cluster_count[i] > 0) {
          station_pos[i] = Pii(cluster_pos_sum[i].first / cluster_count[i], cluster_pos_sum[i].second / cluster_count[i]);
        }
      }
      for (int i = 0; i < planet_num; i++) {
        int nearest_station = -1;
        int nearest_distance = 1000000007;
        for (int j = 0; j < station_num; j++) {
          int dist = (planet_pos[i].first - station_pos[j].first) * (planet_pos[i].first - station_pos[j].first) + (planet_pos[i].second - station_pos[j].second) * (planet_pos[i].second - station_pos[j].second);
          if (dist < nearest_distance) {
            nearest_station = j;
            nearest_distance = dist;
          }
        }
        next_planet_cluster[i] = nearest_station;
      }
      iter_count++;
    } while (planet_cluster != next_planet_cluster || iter_count < 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_id
  que.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) { // planet
      if (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) { // station
      if (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) { // planet
      auto [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) { // station
      auto [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;
}

yukicoder

結果

テストケース

ソースコード