Submission #159638

#	Time	Username	Problem	Language	Result	Execution time	Memory
159638		Peacher29	Rail (IOI14_rail)	C++14	100 / 100	154 ms	60804 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>

using namespace std;

int dH[5000][5000];

int d(int i, int j){
	if(dH[i][j])
		return dH[i][j];
	return dH[i][j]=dH[j][i]=getDistance(i,j);
}

vector<pair<int,int>> pp;

map<int,int> irany; //hol - milyen
int hh[5000];
char c[5000];

void findLocation(int n, int first, int location[], int stype[])
{
	pp.resize(n-1);
	for(int i=0;i<n;i++){
		location[i]=0;
		stype[i]=0;
	}
	location[0]=first;
	stype[0]=1;
	irany[first]=1;
	for(int i=1;i<n;i++){
		pp[i-1]={d(i,0),i};
	}
	sort(pp.begin(),pp.end());
	int x = pp[0].second;
	location[x]=pp[0].first+first;
	irany[location[x]]=2;
	stype[x]=2;
	for(int i=0;i<n;i++){
		if(i!=0 && i!=x){
			if(d(0,i)==d(0,x)+d(x,i)){
				if(d(x,i)<d(0,x)){
					location[i]=location[x]-d(x,i);
					stype[i]=1;
					c[i]='.';
				} else {
					hh[i]=-1;
					c[i]='-';
				}
			} else {
				hh[i]=1;
				c[i]='+';
			}
		}
	}
	int L=x;
	for(pair<int,int>& p : pp){
		if(hh[p.second]==1){
			int k=p.second;
			int z = d(0,k)+d(L,k)-d(0,L);
			int hol = first+d(0,k)-z/2;
			auto it = irany.find(hol);
			if(it==irany.end() || it->second == 1){
				location[k]=first+d(0,k);
				stype[k]=2;
				irany[location[k]]=stype[k];
			} else {
				location[k]=location[L]-d(L,k);
				stype[k]=1;
				irany[location[k]]=stype[k];
			}
			if(location[k]>location[L]){
				L=k;
			}
		}
	}
	L=0;
	for(pair<int,int> p : pp){
		if(hh[p.second]==-1){
			int k=p.second;
			int z = d(x,k)+d(L,k)-d(x,L);
			int hol = location[x]-d(x,k)+z/2;
			auto it = irany.find(hol);
			if(it==irany.end() || it->second == 2){
				location[k]=location[x]-d(x,k);
				stype[k]=1;
				irany[location[k]]=stype[k];
			} else {
				location[k]=location[L]+d(L,k);
				stype[k]=2;
				irany[location[k]]=stype[k];
			}
			if(location[k]<location[L]){
				L=k;
			}
		}
	}
	//cout << "0\n"<<n<<"\n";
	//for(int i=0;i<n;i++) cout << stype[i] << " " << location[i] << " " << c[i] << endl;
}

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