Submission #599085

#	Time	Username	Problem	Language	Result	Execution time	Memory
599085		BT21tata	Rail (IOI14_rail)	C++17	0 / 100	247 ms	200064 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define F first
#define S second
using namespace std;


int dis[5005][5005], t[1000005];

int gdis(int i, int j)
{
	if(dis[i][j]==-1) dis[i][j]=dis[j][i]=getDistance(i, j);
	return dis[i][j];
}

void findLocation(int n, int first, int location[], int stype[])
{
	memset(dis, -1, sizeof(dis));
	vector<pii>d0;
	for(int i=1; i<n; i++)
	{
		d0.pb({gdis(0, i), i});
	}
	sort(all(d0));
	int l=0, r=d0[0].S;
	t[location[0]]=stype[0]=1;
	location[0]=first;

	t[location[d0[0].S]]=stype[d0[0].S]=2;
	location[d0[0].S]=first+d0[0].F;
	for(int i=1; i<n-1; i++)
	{
		int k=d0[i].S;
		bool f=0;
		if(gdis(l, k)>gdis(r, k)) f=1;		
		int e=((l+gdis(l,k))+(r-gdis(r,k)))>>1;
		if(t[e]==2) f=1;
		else if(t[e]==1) f=0;

		if(f)
		{
			stype[k]=1;
			location[k]=location[r]-gdis(r, k);
			t[location[k]]=1;
			if(location[k]<location[l]) l=k;
		}
		else
		{
			stype[k]=2;
			location[k]=location[l]+gdis(l, k);
			t[location[k]]=2;
			if(location[k]>location[r]) r=k;
		}
	}
}

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