Submission #1013955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013955		parsadox2	Rail (IOI14_rail)	C++17	30 / 100	45 ms	1116 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;
	s = -1;
	for(int i = 1 ; i < n ; i++)
	{
		dis[0][i] = getDistance(0 , i);
		//cout << i << " WTF " << dis[0][i] << endl;
		if(s == -1 || dis[0][i] < dis[0][s])
			s = i;
	}
	//cout << "S : " << s << endl;
	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);
		//cout << i << " : " << dis[0][i] << " " << dis[s][i] << endl;
		if(dis[s][i] < dis[0][i])
			L.push_back(i);
		else
		{
			//cout << "WER WER WER WER " << endl;
			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;
	}
}

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

Compilation message (stderr)

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

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