Submission #1065119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065119		Edu175	Rail (IOI14_rail)	C++17	100 / 100	137 ms	204740 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto kjfg:v)cout<<kjfg<<" ";cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
int getDistance(int x, int y);

const ll MAXN=5005,MAXV=1e6+5;
ll mem[MAXN][MAXN];
ll dis(ll x, ll y){
	ll &res=mem[x][y];
	if(res!=-1)return res;
	return res=getDistance(x,y);
}
ll h[MAXV];
void findLocation(int N, int first, int d[], int t[]){
	mset(mem,-1);
	mset(h,-1);
	auto assign=[&](ll i, ll ds, ll ty){
		// cout<<"assign "<<i<<": "<<ds<<" "<<ty<<"\n";
		d[i]=ds;
		t[i]=ty+1;
		h[d[i]]=ty;
	};
	assign(0,first,0);
	vector<ii>a;
	ll n=N;
	if(n==1)return;
	fore(i,1,n)a.pb({dis(0,i),i});
	sort(ALL(a));
	ll mn=a[0].snd;
	assign(mn,d[0]+dis(0,mn),1);
	ll l=0,r=mn;
	for(auto [w,i]:a)if(i!=mn){
		// cout<<i<<": "<<l<<" "<<r<<"\n";
		ll posd=d[0]+dis(0,i);
		ll posi=d[r]-dis(r,i);
		ll m=posi+posd;
		ii c0,c1;
		if(m%2==0&&h[m/2]==1)c1={posi,0};
		else c1={posd,1};
		
		posi=d[0]-(dis(0,i)-2*(d[mn]-d[0]));
		posd=d[l]+dis(l,i);
		m=posi+posd;
		if(m%2==0&&h[m/2]==0)c0={posd,1};
		else c0={posi,0};
		
		// cout<<c0.fst<<","<<c0.snd<<" "<<c1.fst<<","<<c1.snd<<"\n";
		ii c=dis(r,i)==(d[r]-posi)?c0:c1;
		
		assign(i,c.fst,c.snd);
		if(c.fst<d[l])l=i;
		if(c.fst>d[r])r=i;
		// cout<<"\n";
	}
}

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