Submission #136211

#	Time	Username	Problem	Language	Result	Execution time	Memory
136211		vince	Rail (IOI14_rail)	C++14	56 / 100	638 ms	98680 KiB

rail

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <assert.h>
#include "rail.h"

using namespace std;

#define fi first
#define se second
typedef pair<int,int> ii;

const int INF = 1e9;
int dist[5003][5003];
int clos[5003];
int cntt = 0;

void findLocation(int N, int first, int location[], int stype[])
{
	location[0] = first;
	stype[0] = 1;
	if(N == 1)
		return;
	
	for(int i = 0; i < N; i++)
	{
		clos[i] = INF;
		for(int j = i+1; j < N; j++)
		{
			dist[i][j] = getDistance(i,j);
			++cntt;
			dist[j][i] = dist[i][j];
		}
	}

	if(cntt > N*(N-1)/2)
	{
		assert(0);
	}
	if(N > 5000)
		assert(0);

	// for(int i = 0; i < N; i++)
	// {
	// 	for(int j = 0; j < N; j++)
	// 		printf("%d ", dist[i][j]);
	// 	printf("\n");
	// }
	for(int i = 0; i < N; i++)
	{
		int mn = 1e9;
		for(int j = 0; j < N; j++)
		{
			if(i != j && mn > dist[i][j])
			{
				mn = dist[i][j];
				clos[i] = j;
			}
		}

		// printf("%d %d %d\n", i, clos[i], mn);
	}
	int a = clos[clos[0]];
	
	location[clos[0]] = first+dist[clos[0]][0];
	stype[clos[0]] = 2;
	
	location[a] = location[clos[a]]-dist[a][clos[a]];
	stype[a] = 1;

	if(a != clos[clos[a]])
		assert(0);

	for(int i = 0; i < N; i++)
	{
		if(i == a || i == clos[a] || i == 0) continue;
		if(dist[a][i] < dist[clos[a]][i])
		{
			if(a != clos[i] && dist[a][clos[i]] < dist[a][clos[clos[i]]])
			{
				location[i] = location[a]+dist[a][clos[i]]-dist[i][clos[i]];
				stype[i] = 1;
				// printf("KANAN BAWAH %d %d\n", i, location[i]);
			}
			else
			{
				location[i] = location[a]+dist[a][i];
				stype[i] = 2;
				// printf("KANAN ATAS %d %d\n", i, location[i]);
			}
		}
		else
		{
			if(clos[a] != clos[i] && dist[a][clos[i]] < dist[a][clos[clos[i]]])	
			{
				location[i] = location[clos[a]]-dist[clos[a]][clos[i]]+dist[i][clos[i]];
				stype[i] = 2;
				// printf("KIRI ATAS %d %d\n", i, location[i]);
			}
			else
			{
				location[i] = location[clos[a]]-dist[clos[a]][i];
				stype[i] = 1;
				// printf("KIRI BAWAH %d %d\n", i, location[i]);
			}
		}
	}
	// printf("ANS : %d %d\n", a, location[a]);
	// for(int i = 0; i < N; i++)
	// 	printf("	%d %d\n", location[i], stype[i]);

}

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