Submission #385460

#	Time	Username	Problem	Language	Result	Execution time	Memory
385460		Keshi	Rail (IOI14_rail)	C++17	30 / 100	469 ms	100332 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];
	ll cntr = 0;
	for(ll i = 1; i < n; i++){
		if(x == i) continue;
		if(dis[0][i] < dis[x][i]) isr[i] = 1, cntr++;
		if(dis[x][i] < dis[0][x]){
			isr[i] = 1;
			st[i] = 1;
			loc[i] = loc[x] - dis[x][i];
		}
	}
	while(cntr){
		ll y = -1;
		for(ll i = 1; i < n; i++){
			if(!isr[i] || st[i]) continue;
			if(y == -1 || dis[0][y] > dis[0][i]) y = i;
		}
		st[y] = 2;
		loc[y] = dis[0][y];
		cntr--;
		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;
		cntr--;
		for(ll i = 0; i < n; i++){
			if(!isr[i] || st[i]) continue;
			if(dis[y][i] < dis[z][i]){
				st[i] = 1;
				loc[i] = dis[0][i] - dis[0][y];
				cntr--;
			}
		}
	}
	for(ll i = 1; i < n; i++){
		if(!isr[i]) cntr++;
	}
	while(cntr){
		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;
		}
		st[y] = 1;
		loc[y] = dis[0][x] - dis[x][y];
		cntr--;
		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;
		cntr--;
		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]);
				cntr--;
			}
		}
	}
	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