Submission #1013940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013940		parsadox2	Rail (IOI14_rail)	C++17	8 / 100	44 ms	896 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];
}

void Update(int from , int to)
{
	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;
}

void findLocation(int nn , int first, int location[], int stype[])
{
	n = nn;
	loc[0] = first;
	ty[0] = 1;
	s = -1;
	for(int i = 1 ; i < n ; i++)
	{
		dis[0][i] = getDistance(0 , i);
		if(s == -1 || dis[0][i] < dis[0][s])
			s = i;
	}
	Update(0 , s);
	dis[s][0] = dis[0][s];
	for(int i = 1 ; i < n ; i++)  if(i != s)
	{
		dis[s][i] = getDistance(s , i);
		if(dis[s][i] < dis[0][i])
			L.push_back(i);
		else
			R.push_back(i);
	}
	SolveR();
	SolveL();
	for(int i = 0 ; i < n ; i++)
	{
		location[i] = loc[i];
		stype[i] = ty[i];
		//cout << i << " : " << loc[i] << " " << ty[i] << endl;
	}
}

Compilation message (stderr)

rail.cpp: In function 'void SolveR()':
rail.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 1 ; i < R.size() ; i++)
      |                  ~~^~~~~~~~~~

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