제출 #599055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
599055		BT21tata	철로 (IOI14_rail)	C++17	56 / 100	1550 ms	98608 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];

int gdis(int i, int j)
{
	if(dis[i][j]==-1) dis[i][j]=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;
	stype[0]=1;
	location[0]=first;
	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;
		for(int e=0; e<n; e++)
		{
			if(e!=l and e!=k and gdis(l, e)+gdis(e, k)==gdis(l, k))
			{
				f=1;
				break;
			}
		}
		for(int e=0; e<n; e++)
		{
			if(e!=r and e!=k and gdis(r, e)+gdis(e, k)==gdis(r, k))
			{
				f=0;
				break;
			}
		}
		if(f)
		{
			stype[k]=1;
			location[k]=location[r]-gdis(r, k);
			if(location[k]<location[l]) l=k;
		}
		else
		{
			stype[k]=2;
			location[k]=location[l]+gdis(l, k);
			if(location[k]>location[r]) r=k;
		}
	}
}

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