Submission #779279

#	Time	Username	Problem	Language	Result	Execution time	Memory
779279		fatemetmhr	Rail (IOI14_rail)	C++17	56 / 100	311 ms	98672 KiB

rail

//  ~ Be Name Khoda ~  //

#include "rail.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int dis[maxn5][maxn5], mn[maxn5];
bool mark[maxn5];


void findLocation(int n, int first, int location[], int stype[])
{
	if(n == 1){
		location[0] = first;
		stype[0] = 1;
		return;
	}
	for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++)
		dis[i][j] = dis[j][i] = getDistance(i, j);

	for(int i = 0; i < n; i++){
		mn[i] = i == n - 1 ? 0 : i + 1;
		for(int j = 0; j < n; j++) if(j != i && dis[i][j] < dis[i][mn[i]])
			mn[i] = j;
	}

	int x = mn[0];
	int y = mn[x];
	location[y] = first + dis[0][x] - dis[x][y];
	stype[y] = 1;
	location[x] = first + dis[0][x];
	stype[x] = 2;

	for(int i = 0; i < n; i++)
		//cout << i << ' ' << mn[i] << endl;

	for(int i = 0; i < n; i++) if(!mark[i] && i == mn[mn[i]]){
		int v = mn[i];
		//cout << "here " << i << ' ' << v << endl;
		mark[i] = mark[v] = true;
		int u = i;
		if(u != x && u != y){
			if(dis[y][i] < dis[x][i]){
				if(dis[y][u] > dis[y][v])
					swap(u, v);
				location[u] = location[y] + dis[u][y];
				location[v] = location[u] - dis[u][v];
				stype[u] = stype[x];
				stype[v] = stype[y];
			}
			else{
				if(dis[x][u] < dis[x][v])
					swap(u, v);
				location[v] = location[x] - dis[x][v];
				location[u] = location[v] + dis[u][v];
				stype[u] = stype[x];
				stype[v] = stype[y];
			}
		}
		else if(stype[v] == 2)
			swap(u, v);
		for(int j = 0; j < n; j++) if(!mark[j]){
			//cout << "ha? " << j << ' ' << u << ' ' << v << endl;
			if(mn[j] == v){
				location[j] = location[v] + dis[j][v];
				mark[j] = true;
				stype[j] = stype[u];
			}
			if(mn[j] == u){
				location[j] = location[u] - dis[j][u];
				stype[j] = stype[v];
				mark[j] = true;
			}
		}
	}
	return;
	//for(int i = 0; i < n; i++)
		//cout << "* " << location[i] << ' ' << stype[i] << endl;
	return;
}

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