제출 #53168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
53168		KieranHorgan	철로 (IOI14_rail)	C++17	0 / 100	2527 ms	99028 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

int dist[5005][5005];
int get(int i, int j) {
	if(dist[i][j] != 0) return dist[i][j];
	return dist[i][j] = dist[j][i] = getDistance(i, j);
}
vector<int> xIsClosest[5005];
int negLoc[5005];
int vis[5005];

void findLocation(signed N, signed first, signed location[], signed stype[]) {
	for(int i = 0; i < N; i++)
		for(int j = 0; j < i; j++)
			get(i, j);

	vector<pair<int, int>> z;
	for(int i = 0; i < N; i++) {
		z.clear();
		for(int j = 0; j < N; j++) {
			if(i==j) continue;
			z.push_back({get(i,j), j});
		}
		sort(z.begin(), z.end());
		xIsClosest[z[0].second].push_back(i);
		// cerr << i << "->" << z[0].second << endl;
	}

	queue<pair<int, int>> q;
	q.push({0, 1});
	int mi = 0;
	while(!q.empty()) {
		int i = q.front().first;
		int t = q.front().second;
		vis[i]=1;
		stype[i] = t;
		// cerr << i << ": " << t << " " << negLoc[i] << endl;
		q.pop();
		for(auto j: xIsClosest[i]) {
			if(vis[j]) continue;
			negLoc[j] = negLoc[i] + (t==1?get(i,j):-get(i,j));
			mi = min(mi, negLoc[j]);
			q.push({j, t+(t==1)-(t==2)});
		}
	}

	cerr << endl;
	for(int i = 0; i < N; i++) {
		location[i] = -mi+negLoc[i]+first;
	}
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44