제출 #1014092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1014092		parsadox2	철로 (IOI14_rail)	C++17	56 / 100	327 ms	98808 KiB

rail

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

using namespace std;

const int N = 5e3 + 10;
int dis[N][N] , n , f , s , loc[N] , ty[N];
vector <int> L , R;

bool cmpR(int a , int b)
{
	return dis[0][a] < dis[0][b];
}

bool cmpL(int a , int b)
{
	return dis[s][a] < dis[s][b];
}

void Update(int from , int to)
{
	//cout << from << " -> " << to << endl;
	ty[to] = 3 - ty[from];
	if(ty[from] == 1)
		loc[to] = loc[from] + dis[from][to];
	else
		loc[to] = loc[from] - dis[from][to];
}

/*void SolveR()
{
	if(R.empty())
		return;
	sort(R.begin() , R.end() , cmpR);
	int las = R[0];
	Update(0 , las);
	for(int i = 1 ; i < R.size() ; i++)
	{
		int now = R[i];
		dis[las][now] = getDistance(las , now);
		if(dis[las][now] < dis[0][las])
			Update(las , now);
		else
		{
			Update(0 , now);
			las = now;
		}
	}
}

void SolveL()
{
	if(L.empty())
		return;
	sort(L.begin() , L.end() , cmpL);
	int las = 0;
	for(int i = 0 ; i < L.size() ; i++)
	{
		int now = L[i];
		if(dis[s][now] < dis[s][0])
		{
			Update(s , now);
			continue;
		}
		dis[las][now] = getDistance(las , now);
		if(dis[las][now] < dis[s][las])
			Update(las , now);
		else
		{
			Update(s , now);
			las = now;
		}
	}
}*/

void findLocation(int nn , int first, int location[], int stype[])
{
	n = nn;
	loc[0] = first;
	ty[0] = 1;
	for(int i = 0 ; i < n ; i++)  for(int j = i + 1 ; j < n ; j++)
	{
		int x = getDistance(i , j);
		dis[i][j] = dis[j][i] = x;
	}
	vector <int> vec;
	for(int i = 1 ; i < n ; i++)
		vec.push_back(i);
	sort(vec.begin() , vec.end() , cmpR);
	for(int i = 0 ; i < n - 1 ; i++)
	{
		int las = 0;
		for(int j = 0 ; j < i ; j++)  if(dis[0][vec[j]] + dis[vec[j]][vec[i]] == dis[0][vec[i]])
			las = vec[j];
		Update(las , vec[i]);
	}
	for(int i = 0 ; i < n ; i++)
	{
		location[i] = loc[i];
		stype[i] = ty[i];
		//cout << i << " " << ty[i] << " " << loc[i] << endl;
	}
}

/*
3
11
1 4
1 5
2 6
1 7
2 8
1 9
2 3
1 2
2 1
2 10
1 0
*/

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