結果

問題 No.5007 Steiner Space Travel
ユーザー yas_yasyuyas_yasyu
提出日時 2023-04-26 02:49:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 120 ms / 1,000 ms
コード長 3,849 bytes
コンパイル時間 5,094 ms
コンパイル使用メモリ 273,108 KB
実行使用メモリ 4,376 KB
スコア 1,333,715
最終ジャッジ日時 2023-04-26 02:49:39
合計ジャッジ時間 10,695 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 115 ms
4,372 KB
testcase_01 AC 114 ms
4,368 KB
testcase_02 AC 114 ms
4,372 KB
testcase_03 AC 115 ms
4,368 KB
testcase_04 AC 115 ms
4,372 KB
testcase_05 AC 114 ms
4,368 KB
testcase_06 AC 114 ms
4,368 KB
testcase_07 AC 114 ms
4,368 KB
testcase_08 AC 115 ms
4,368 KB
testcase_09 AC 116 ms
4,376 KB
testcase_10 AC 115 ms
4,368 KB
testcase_11 AC 115 ms
4,372 KB
testcase_12 AC 115 ms
4,372 KB
testcase_13 AC 115 ms
4,372 KB
testcase_14 AC 114 ms
4,372 KB
testcase_15 AC 114 ms
4,372 KB
testcase_16 AC 114 ms
4,372 KB
testcase_17 AC 114 ms
4,368 KB
testcase_18 AC 114 ms
4,372 KB
testcase_19 AC 120 ms
4,372 KB
testcase_20 AC 115 ms
4,368 KB
testcase_21 AC 115 ms
4,368 KB
testcase_22 AC 113 ms
4,372 KB
testcase_23 AC 114 ms
4,372 KB
testcase_24 AC 114 ms
4,372 KB
testcase_25 AC 114 ms
4,372 KB
testcase_26 AC 114 ms
4,368 KB
testcase_27 AC 114 ms
4,372 KB
testcase_28 AC 115 ms
4,368 KB
testcase_29 AC 113 ms
4,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);

const double TIME_LIMIT = 0.95;

struct Planet {
    int a;
    int b;
    int idx;
    Planet(int _a, int _b, int _idx) {
        a = _a;
        b = _b;
        idx = _idx;
    }
    Planet(const Planet &old) {
        a = old.a;
        b = old.b;
        idx = old.idx;
    }
};

int N, M;
vector<Planet> planet;
vector<Planet> station;

const int A = 5;
/*Target to minimize */
ll energy = 0;
vector<pair<int, int>> ans;

vector<vector<ll>> FloydWarshall(vector<vector<ll>>& distances)
{
	const size_t v = distances.size();

	for (size_t i = 0; i < v; ++i)
	{
		for (size_t frm = 0; frm < v; ++frm)
		{
			for (size_t to = 0; to < v; ++to)
			{
				if ((distances[frm][i] < INF) && (distances[i][to] < INF))
				{
					distances[frm][to] = min(distances[frm][to], (distances[frm][i] + distances[i][to]));
				}
			}
		}
	}

	return distances;
}

void Input() {
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        planet.push_back(Planet(a, b, i + 1));
    }
    return;
}

void OutputStation() {
    for(int i = 0; i < M; i++) {
        cout << station[i].a << " " << station[i].b << endl;
    }
    return;
}

void OutputWayPoint(pair<int, int> wayPoint) { cout << wayPoint.first << " " << wayPoint.second+1 << endl; }

void OutputRoute() {
    int V = (int)ans.size();
    cout << V << endl;

    for(int i = 0; i < V; i++) {
        OutputWayPoint(ans[i]);
    }

    return;
}

ll Distance(Planet pa, Planet pb)
{
	ll a = (pa.a - pb.a);
	ll b = (pa.b - pb.b);
	return a*a + b*b;
}

void Pick(int &a, int &b)
{
	while(true)
	{
		a = rand()%ans.size();
		b = rand()%ans.size();
		if(a > b) swap(a, b);
		if (a+1 == b || b == ans.size()-1)
		{
			continue;
		}
		return;
	}
}

void EdgeSwap(int a, int b)
{
	a++;
	while(a < b)
	{
		swap(ans[a], ans[b]);
		a++;
		b--;
	}
}

void TwoOpt(vector<vector<ll>> distances, int cnt)
{
	do
	{
		int a, b;
		Pick(a, b);
		int na, nb;
		na = (a+1)%(ans.size());
		nb = (b+1)%(ans.size());
		

		Planet Pa  = (ans[ a].first == 1)? planet[ans[ a].second] : station[ans[ a].second];
		Planet Pb  = (ans[ b].first == 1)? planet[ans[ a].second] : station[ans[ b].second];
		Planet Pna = (ans[na].first == 1)? planet[ans[na].second] : station[ans[na].second];
		Planet Pnb = (ans[nb].first == 1)? planet[ans[nb].second] : station[ans[nb].second];
		
		ll beforeDist = Distance(Pa, Pna) + Distance(Pb, Pnb);
		ll afterDist  = Distance(Pa, Pb) + Distance(Pna, Pnb);
		if (beforeDist > afterDist)
		{
			EdgeSwap(a, b);
		}
	} while (--cnt);
}

void solve() {
    for(int i = 1; i < M + 1; i++) {
        station.push_back(Planet(i*120, i*120, i));
    }

	vector<vector<ll>> distances(N, vector(N, INF));

	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < N; j++)
		{
			distances[i][j] = Distance(planet[i], planet[j]);
		}
	}
	FloydWarshall(distances);

	set<int> bef;
	int frmIdx = 0;
	ans.push_back(pair<int, int>(1, 0));
	for(int i = 0; i < N; i++)
	{
		ll minDist = INF;
		int nxtIdx = -1;
		bef.insert(frmIdx + 1);

		for(int toIdx = 0; toIdx < N; toIdx++)
		{
			if(bef.find(toIdx+1) != bef.end())
			{
				continue;
			}
			if(minDist > distances[frmIdx][toIdx])
			{
				minDist = distances[frmIdx][toIdx];
				nxtIdx = toIdx;
			}
		}
		if (nxtIdx == -1) continue;
		ans.push_back(pair<int, int>(1, nxtIdx));
		frmIdx = nxtIdx;
	}
	for(int i = 0; i < M; i++)
	{
		ans.push_back(pair<int, int>(2, i));
	}
	ans.push_back(pair<int, int>(1, 0));

	TwoOpt(distances, 1000000);

    return;
}

int main() {
	srand(time(NULL));
    Input();

    solve();

    OutputStation();
    OutputRoute();

    return 0;
}
0