Submission #385465

#	Time	Username	Problem	Language	Result	Execution time	Memory
385465		Keshi	Rail (IOI14_rail)	C++17	30 / 100	470 ms	100588 KiB

rail

//In the name of God
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 5100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll dis[maxn][maxn];
bool isr[maxn];

void findLocation(int n, int first, int loc[], int st[]){
	for(ll i = 0; i < n; i++){
		for(ll j = i + 1; j < n; j++){
			dis[i][j] = dis[j][i] = getDistance(i, j);
		}
	}
	ll x = 1;
	for(ll i = 1; i < n; i++){
		if(dis[0][i] < dis[0][x]) x = i;
	}
	st[0] = 1;
	st[x] = 2;
	isr[x] = 1;
	loc[x] = dis[0][x];
	for(ll i = 1; i < n; i++){
		if(x != i && dis[x][i] < dis[0][x]){
			st[i] = 1;
			loc[i] = dis[0][x] - dis[x][i];
		}
		if(x == i || dis[0][i] != dis[0][x] + dis[x][i]) isr[i] = 1;
	}
	while(true){
		ll y = -1;
		for(ll i = 1; i < n; i++){
			if(st[i]) continue;
			if(!isr[i]) continue;
			if(y == -1 || dis[0][y] > dis[0][i]) y = i;
		}
		if(y == -1) break;
		st[y] = 2;
		loc[y] = dis[0][y];
		ll z = 0;
		for(ll i = 0; i < n; i++){
			if(i == y) continue;
			if(dis[y][i] < dis[y][z]) z = i;
		}
		if(st[z]) continue;
		loc[z] = 2 * dis[0][y] - dis[0][z];
		st[z] = 1;
		for(ll i = 0; i < n; i++){
			if(st[i]) continue;
			if(!isr[i]) continue;
			if(dis[y][i] < dis[z][i]){
				st[i] = 1;
				loc[i] = dis[0][i] - dis[0][y];
			}
		}
	}
	while(true){
		ll y = -1;
		for(ll i = 1; i < n; i++){
			if(isr[i] || st[i]) continue;
			if(y == -1 || dis[x][y] > dis[x][i]) y = i;
		}
		if(y == -1) break;
		st[y] = 1;
		loc[y] = dis[0][x] - dis[x][y];
		ll z = 0;
		for(ll i = 0; i < n; i++){
			if(i == y) continue;
			if(dis[y][i] < dis[y][z]) z = i;
		}
		if(st[z]) continue;
		loc[z] = dis[0][x] - (2 * dis[x][y] - dis[x][z]);
		st[z] = 2;
		for(ll i = 0; i < n; i++){
			if(isr[i] || st[i]) continue;
			if(dis[y][i] < dis[z][i]){
				st[i] = 2;
				loc[i] = dis[0][x] - (2 * dis[x][y] - dis[x][i]);
			}
		}
	}
	loc[0] = 0;
	for(ll i = 0; i < n; i++){
		loc[i] += first;
	}
	return;
}

/*int main(){
    fast_io;



    return 0;
}*/

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