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

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	fky_
提出日時	2022-07-30 14:38:38
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 1,000 ms
コード長	5,123 bytes
コンパイル時間	2,142 ms
実行使用メモリ	3,560 KB
スコア	6,057,324
最終ジャッジ日時	2022-07-30 14:38:42
合計ジャッジ時間	3,972 ms
ジャッジサーバーID （参考情報）	judge14 / judge10
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 3,556 KB
testcase_01	AC	2 ms 3,400 KB
testcase_02	AC	2 ms 3,548 KB
testcase_03	AC	2 ms 3,472 KB
testcase_04	AC	2 ms 3,400 KB
testcase_05	AC	2 ms 3,556 KB
testcase_06	AC	2 ms 3,472 KB
testcase_07	AC	2 ms 3,472 KB
testcase_08	AC	2 ms 3,404 KB
testcase_09	AC	2 ms 3,472 KB
testcase_10	AC	2 ms 3,536 KB
testcase_11	AC	2 ms 3,404 KB
testcase_12	AC	2 ms 3,552 KB
testcase_13	AC	2 ms 3,404 KB
testcase_14	AC	2 ms 3,400 KB
testcase_15	AC	2 ms 3,552 KB
testcase_16	AC	2 ms 3,508 KB
testcase_17	AC	2 ms 3,508 KB
testcase_18	AC	2 ms 3,524 KB
testcase_19	AC	2 ms 3,456 KB
testcase_20	AC	2 ms 3,424 KB
testcase_21	AC	2 ms 3,404 KB
testcase_22	AC	2 ms 3,472 KB
testcase_23	AC	2 ms 3,456 KB
testcase_24	AC	2 ms 3,500 KB
testcase_25	AC	2 ms 3,408 KB
testcase_26	AC	2 ms 3,524 KB
testcase_27	AC	2 ms 3,556 KB
testcase_28	AC	2 ms 3,560 KB
testcase_29	AC	2 ms 3,500 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define RFOR(i, a, b) for (int i = a; i >= (b); i--)
#define range(a) a.begin(), a.end()
#define endl "\n"
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
#define MP make_pair
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
using P = pair<int, int>;
const long long INF = 1LL<<60;
void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }

struct xorshift128{
    const unsigned int ini_x = 123456789, ini_y = 362436069, ini_z = 521288629, ini_w = 88675123;
    unsigned int x, y, z, w;
    
    xorshift128() {}

    // シードによってx,y,z,wを初期化 ... initialize x,y,z,w by seed
    void set_seed(unsigned int seed){
        x = ini_x, y = ini_y, z = ini_z, w = ini_w ^ seed;
    }

    unsigned int randint(){
        unsigned int t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }

    // [0,r)の範囲の整数で乱数発生 ... generate random integer in [0,r)
    unsigned int randint(unsigned int r){
        assert(r != 0);
        return randint() % r;
    }

    // [l,r)の範囲の整数で乱数発生 ... generate random integer in [l,r)
    unsigned int randint(unsigned int l, unsigned int r){
        assert(r > l);
        return l + randint(r-l);
    }

    // 長さnの順列をランダムに生成し、その前k個分を出力する ... generate a random permutation of size n, and return the first k
    vector<int> randperm(int n, int k){
        assert(k >= 0 && k <= n);
        vector<int> ret(n);
        for(int i = 0; i < n; i++){
            ret[i] = i;
        }
        for(int i = 0; i < k; i++){
            swap(ret[i], ret[randint(i, n)]);
        }
        return vector<int>(ret.begin(), ret.begin() + k);
    }

    // [0,1]の範囲の実数で乱数発生 ... generate random real number in [0,1]
    double uniform(){
        return double(randint()) * 2.3283064370807974e-10;
    }

    // [0,r]の範囲の実数で乱数発生 ... generate random real number in [0,r]
    double uniform(double r){
        assert(r >= 0.0);
        return uniform() * r;
    }

    // [l,r]の範囲の実数で乱数発生 ... generate random real number in [l,r]
    double uniform(double l, double r){
        assert(r >= l);
        return l + uniform(r - l);
    }
};

xorshift128 Random;

const int64_t CYCLES_PER_SEC = 2800000000;

struct Timer {
	int64_t start;
	Timer() { reset(); }
	void reset() { start = getCycle(); }
	void plus(double a) { start -= (a * CYCLES_PER_SEC); }
	inline double get() { return (double)(getCycle() - start) / CYCLES_PER_SEC; }
	inline int64_t getCycle() {
		uint32_t low, high;
		__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
		return ((int64_t)low) | ((int64_t)high << 32);
	}
};

Timer timer;

ll get_dist(P a, P b){
    return round(hypot(abs(a.first - b.first), abs(a.second - b.second)));
}

int N = 100, M = 8, alpha = 5;
vector<pair<int, int>> planet(100);

struct Game{
    vector<pair<int, int>> station;
    vector<int> next;
    ll score;
    Game() { init(); }
    void init(){
        cin >> N >> M;
        FOR(i,0,N){
            cin >> planet[i].first >> planet[i].second;
        }
        station.resize(M, {-1, -1});
        next.resize(N, -1);
        score = 0LL;
    }

    void first_route(){
        // 初期化
        next[0] = 1, next[1] = 0;
        score = 2 * get_dist(planet[0], planet[1]);

        // 挿入
        FOR(s,2,N){
            ll dlt_dis = INF, min_bdx = -1;
            int bdx = 0;
            while(bdx > 0 || min_bdx == -1){
                // i, i + 1の間に挿入
                int adx = next[bdx];
                ll n_dis = get_dist(planet[bdx], planet[s]) + get_dist(planet[s], planet[adx]) - get_dist(planet[bdx], planet[adx]);
                if(n_dis < dlt_dis){
                    dlt_dis = n_dis;
                    min_bdx = bdx;
                }
                // cerr << bdx << " " << n_dis << endl;
                bdx = next[bdx];
            }
            // cerr << endl;

            next[s] = next[min_bdx], next[min_bdx] = s;
        }

        int now = 0;
        do{
            score = pow(alpha, 2) * get_dist(planet[now], planet[next[now]]);
            now = next[now];
        } while (now > 0);
        return;
    }

    void output(){
        FOR(i,0,M){
            cout << "0 0" << endl;
        }

        cout << N + 1 << endl;
        int now = 0;
        do{
            cout << 1 << " " << now + 1 << endl;
            now = next[now];
        } while (now > 0);
        cout << "1 1" << endl;
    }
};

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	timer.reset();
	double TIMELIMIT = 1.0;
	random_device rnd;     // 非決定的な乱数生成器
	unsigned long long sd = (unsigned long long)rnd(); 
	Random.set_seed(sd);

    Game game;
    game.init();
    game.first_route();
    game.output();

    return 0;
}

yukicoder

結果

テストケース

ソースコード