結果

問題 No.5007 Steiner Space Travel
ユーザー platinumplatinum
提出日時 2022-07-30 17:19:58
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 354 ms / 1,000 ms
コード長 4,389 bytes
コンパイル時間 2,304 ms
実行使用メモリ 6,952 KB
スコア 6,810,864
最終ジャッジ日時 2022-07-30 17:20:12
合計ジャッジ時間 12,929 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)

using namespace std;
using LL = long long;
using P = pair<int,int>;
using vv = vector<vector<int>>;
const int INF = (int)1e9;
const LL LINF = (LL)1e18;

vector<P> c;
struct route{
	vector<P> travel;
	int dist;
	route(int dist, vector<P> travel){
		this->dist = dist;
		this->travel = travel;
	}
};

vector<P> calc_centers(vv &planets){
	int m = planets.size();
	vector<P> centers;
	rep(i,m){
		int siz = planets[i].size();
		int x = 0, y = 0;
		rep(j,siz){
			int k = planets[i][j];
			x += c[k].first, y += c[k].second;
		}
		x /= siz, y /= siz;
		centers.emplace_back(x, y);
	}
	return centers;
}

vv separate(int M, int dist){
	vv planets;
	int siz = c.size();
	vector<int> selected(siz);
	while(1){
		if((int)planets.size() == M) break;
		int start = -1;
		rep(i,siz){
			if(!selected[i]){
				start = i;
				break;
			}
		}
		if(start == -1) break;
		vector<int> add;
		add.emplace_back(start);
		selected[start] = 1;
		int sx = c[start].first, sy = c[start].second;
		rep(i,siz){
			if(selected[i]) continue;
			int x = c[i].first, y = c[i].second;
			int d = (sx - x) * (sx - x) + (sy - y) * (sy - y);
			if(d > dist) continue;
			add.emplace_back(i);
			selected[i] = 1;
		}
		planets.emplace_back(add);
	}
	vector<P> centers = calc_centers(planets);
	rep(i,siz){
		if(selected[i]) continue;
		int min_dist = INF, group = -1;
		rep(j,(int)centers.size()){
			int cx = centers[j].first, cy = centers[j].second;
			int x = c[i].first, y = c[i].second;
			int d = (cx - x) * (cx - x) + (cy - y) * (cy - y);
			if(d < min_dist){
				min_dist = d;
				group = j;
			}			
		}
		planets[group].emplace_back(i);
	}
	return planets;
}

route pathway(vv &planets){
	vector<P> travel;
	int min_dist = INF;
	int m = planets.size();
	vector<P> centers = calc_centers(planets);
	int dist = 0;
	rep(i,m){
		int cx = centers[i].first, cy = centers[i].second;
		for(auto p : planets[i]){
			int x = c[p].first, y = c[p].second;
			int d = (cx - x) * (cx - x) + (cy - y) * (cy - y);
			dist += d * 10;			
		}
	}
	vector<int> ord(m-1);
	rep(i,m-1) ord[i] = i + 1;
	do{
		vector<P> res;
		vector<int> now_order = ord;
		now_order.emplace_back(0);
		int stations_dist = 0;
		for(int i = m - 1; i >= 0; i--){
			int k = now_order[i];
			int cx = centers[k].first, cy = centers[k].second;
			if(i > 0){
				int new_k = now_order[i-1];
				int new_cx = centers[new_k].first;
				int new_cy = centers[new_k].second;
				stations_dist += (cx - new_cx) * (cx - new_cx)
				+ (cy - new_cy) * (cy - new_cy);
			}
			else{
				int new_k = 0;
				int new_cx = centers[new_k].first;
				int new_cy = centers[new_k].second;
				stations_dist += (cx - new_cx) * (cx - new_cx)
				+ (cy - new_cy) * (cy - new_cy);
			}
		}
		if(stations_dist + dist < min_dist){
			min_dist = stations_dist + dist;
			for(int i = m - 1; i >= 0; i--){
				int k = now_order[i];
				if(k == 0){
					res.emplace_back(1, 1);
					res.emplace_back(2, 1);
				}
				for(auto p : planets[k]){
					res.emplace_back(1, p + 1);
					res.emplace_back(2, k + 1);
				}
				if(i == 0){
					res.emplace_back(2, 1);
					res.emplace_back(1, 1);
				}
				else{
					int new_k = now_order[i-1];
					res.emplace_back(2, new_k + 1);
				}
			}
			travel = res;
		}
	}while(next_permutation(ord.begin(), ord.end()));
	route best_pathway(min_dist, travel);
	return best_pathway;
}

int main(){
	//FILE *in = freopen("in.txt", "r", stdin);
	//FILE *out = freopen("out.txt", "w", stdout);

	int N, M;
	cin >> N >> M;
	rep(i,N){
		int a, b;
		cin >> a >> b;
		c.emplace_back(a, b);
	}
	int min_dist = INF;
	vector<P> travel;
	vv final_planets;
	for(int d = 100; d <= 100000; d += 100){
		vv planets = separate(M, d);
		route best_route = pathway(planets);
		if(best_route.dist < min_dist){
			min_dist = best_route.dist;
			travel = best_route.travel;
			final_planets = planets;
		}
	}
	vector<P> stations = calc_centers(final_planets);
	int siz = stations.size();
	rep(i,siz){
		cout << stations[i].first << " " << stations[i].second << endl;
	}
	rep(i,M-siz){
		cout << 1000 << " " << 1000 << endl;
	}
	int V = travel.size();
	cout << V << endl;
	rep(i,V){
		cout << travel[i].first << " " << travel[i].second << endl;
	}
	/*
	cout << endl;
	rep(i,(int)final_planets.size()){
		for(auto p : final_planets[i]){
			cout << p << " ";
		}
		cout << endl;
	}
	*/

	return 0;
}
0