Submission #115401

#	Time	Username	Problem	Language	Result	Execution time	Memory
115401		faustaadp	Rail (IOI14_rail)	C++17	30 / 100	973 ms	262144 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,d[5050][5050],cal,j;
pair<ll,ll> A[5050][5050];
vector<pair<ll,ll> > isi;
ll pos[5050];
ll tipe[5050];
ll z[5050];
void findLocation(int N, int first, int location[], int stype[])
{
	//if(N>100)
	//	while(1);
	pos[0]=first;
	tipe[0]=1;
//	if(N==1)
//		return ;
	for(i=0;i<N;i++)
		for(j=i+1;j<N;j++)
		{
			d[i][j]=getDistance(i,j);
			d[j][i]=d[i][j];
		}
	for(i=0;i<N;i++)
	{
		for(j=0;j<N;j++)
			A[i][j]=mp(d[i][j],j);
		sort(A[i],A[i]+N);
	//	cout<<i<<" "<<A[i][1].se<<"()\n";
	}
	for(i=0;i<N;i++)
		for(j=i+1;j<N;j++)
			if(A[i][1].se==j&&A[j][1].se==i)
				isi.pb(mp(i,j));
	for(i=0;i<isi.size();i++)
	{
		if(isi[i].fi==A[0][1].se||isi[i].se==A[0][1].se)
		{
			if(isi[i].fi==A[0][1].se)
				swap(isi[i].fi,isi[i].se);
			swap(isi[0],isi[i]);
			break;
		}
	}
	tipe[isi[0].fi]=1;
	tipe[isi[0].se]=2;

	pos[isi[0].se]=pos[0]+d[0][isi[0].se];
	pos[isi[0].fi]=pos[isi[0].se]-d[isi[0].se][isi[0].fi];
	for(i=1;i<isi.size();i++)
	{
	//	cout<<"( <3 ) "<<isi[i].fi<<" "<<isi[i].se<<"\n";
	//	x[0][pas]+
		if(d[isi[0].fi][isi[i].fi]==(d[isi[0].fi][isi[0].se]+d[isi[0].se][isi[i].fi]))
		{
			if(d[isi[0].fi][isi[i].fi]>d[isi[0].fi][isi[i].se])
				swap(isi[i].fi,isi[i].se);
			pos[isi[i].fi]=pos[isi[0].se]-d[isi[0].se][isi[i].fi];
			pos[isi[i].se]=pos[isi[i].fi]+d[isi[i].se][isi[i].fi];
		}
		else
		{
			if(d[isi[0].fi][isi[i].fi]<d[isi[0].fi][isi[i].se])
				swap(isi[i].fi,isi[i].se);
			pos[isi[i].se]=pos[isi[0].fi]+d[isi[0].fi][isi[i].se];
			pos[isi[i].fi]=pos[isi[i].se]-d[isi[i].se][isi[i].fi];
		}
		tipe[isi[i].fi]=1;
		tipe[isi[i].se]=2;
	}
	for(i=0;i<isi.size();i++)
	{
		z[isi[i].fi]=1;
		z[isi[i].se]=1;
	//	cout<<isi[i].fi<<" "<<isi[i].se<<"_\n";
	}
	for(i=0;i<isi.size();i++)
	{
		//break;
		for(j=0;j<N;j++)
		{
			if(z[j])continue;
			if(A[j][1].se==isi[i].se)
			{
				tipe[j]=1;
				pos[j]=pos[isi[i].se]-d[j][isi[i].se];
			}
		}
		for(j=0;j<N;j++)
		{
			if(z[j])continue;
			if(A[j][1].se==isi[i].fi)
			{
				tipe[j]=2;
				pos[j]=pos[isi[i].fi]+d[j][isi[i].fi];
			}
		}
		//cout<<"( <3 )\n"<<isi[i].fi<<" "<<isi[i].se<<"\n";
		//cout<<pos[isi[i].fi]<<" "<<pos[isi[i].se]<<"\n";
		//cout<<"\n";
	}
	for(i=0;i<N;i++)
	{
	//	cout<<i<<"  "<<tipe[i]<<" "<<pos[i]<<"\n";
		location[i]=pos[i];
		stype[i]=tipe[i];
	}
}	
	

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:40:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<isi.size();i++)
          ~^~~~~~~~~~~
rail.cpp:55:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=1;i<isi.size();i++)
          ~^~~~~~~~~~~
rail.cpp:76:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<isi.size();i++)
          ~^~~~~~~~~~~
rail.cpp:82:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<isi.size();i++)
          ~^~~~~~~~~~~

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