Submission #64512

#	Time	Username	Problem	Language	Result	Execution time	Memory
64512		TadijaSebez	Rail (IOI14_rail)	C++11	100 / 100	160 ms	32252 KiB

rail

#include "rail.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define pb push_back
const int N=5050;
int dist[N][N];
int Get(int i, int j)
{
	if(i>j) return Get(j,i);
	if(dist[i][j]) return dist[i][j];
	return dist[i][j]=getDistance(i,j);
}
map<int,int> dir;
int fir=1;
bool comp1(int i, int j){ return Get(0,i)<Get(0,j);}
bool comp2(int i, int j){ return Get(fir,i)<Get(fir,j);}
void findLocation(int n, int st, int d[], int t[])
{
	d[0]=st;
	t[0]=1;
	dir[d[0]]=t[0];
	if(n==1) return;
	int i,j;fir=1;
	vector<int> left,right;
	for(i=2;i<n;i++) if(Get(0,fir)>Get(0,i)) fir=i;
	d[fir]=st+Get(0,fir);
	t[fir]=2;
	dir[d[fir]]=t[fir];
	for(i=1;i<n;i++)
	{
		if(i==fir) continue;
		if(Get(0,i)==d[fir]-d[0]+Get(fir,i))
		{
			if(d[fir]-d[0]>Get(fir,i))
			{
				t[i]=1;
				d[i]=d[fir]-Get(fir,i);
				dir[d[i]]=t[i];
			}
			else left.pb(i);
		}
		else right.pb(i);
	}
	sort(left.begin(),left.end(),comp2);
	sort(right.begin(),right.end(),comp1);
	int l=0,r=fir;
	for(i=0;i<left.size();i++)
	{
		int x=left[i];
		int val=(d[r]-d[l]+Get(l,x)-Get(r,x))/2;
		if(dir[d[l]+val]==1)
		{
			d[x]=d[l]+Get(l,x);
			t[x]=2;
			dir[d[x]]=t[x];
		}
		else
		{
			d[x]=d[r]-Get(r,x);
			t[x]=1;
			dir[d[x]]=t[x];
			l=x;
		}
	}
	l=0;r=fir;
	for(i=0;i<right.size();i++)
	{
		int x=right[i];
		int val=(d[r]-d[l]+Get(r,x)-Get(l,x))/2;
		if(dir[d[r]-val]==2)
		{
			d[x]=d[r]-Get(r,x);
			t[x]=1;
			dir[d[x]]=t[x];
		}
		else
		{
			d[x]=d[l]+Get(l,x);
			t[x]=2;
			dir[d[x]]=t[x];
			r=x;
		}
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:50:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<left.size();i++)
          ~^~~~~~~~~~~~
rail.cpp:69:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<right.size();i++)
          ~^~~~~~~~~~~~~
rail.cpp:26:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;fir=1;
        ^

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