Submission #550887

#	Time	Username	Problem	Language	Result	Execution time	Memory
550887		CSQ31	Rail (IOI14_rail)	C++17	100 / 100	114 ms	60692 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
int d[5001][5001];
int ask(int i,int j){
	if(i==j)return 0;
	if(d[i][j])return d[i][j];
	d[i][j] = d[j][i] = getDistance(i,j);
	return d[i][j];
}
void findLocation(int n, int f, int location[], int stype[])
{
	location[0] = f;
	stype[0] = 1;
	
	//find the closest guy to 0
	int mnn = 1e9;
	int x = 0;
	vector<int>l,r;
	for(int i=1;i<n;i++){
		if(mnn > ask(0,i)){
			mnn = ask(0,i);
			x = i;
		}
	}
	stype[x] = 2;
	location[x] = f + ask(0,x);
	for(int i=0;i<n;i++){
		if(i!=0 && i!=x){
			if(ask(0,i) == ask(0,x) + ask(x,i))l.push_back(i);
			else r.push_back(i);
		}
	}
	vector<pair<int,int>>a;
	for(int y:r)a.push_back({ask(0,y),y});
	sort(a.begin(),a.end());
	int last = x;
	map<int,bool>seen;
	for(auto Z : a){
		int z = Z.second;
		//try the path x->y->z
		//will always be a upper bound to x->z
		int m = ask(0,last) + ask(last,z);
		m-=ask(0,z);
		m/=2;
		if(location[last] - m>=0 && seen[location[last] - m]){
			stype[z] = 1;
			location[z] = location[last] - ask(last,z);
		}else{
			stype[z] = 2;
			location[z] = location[0] + ask(0,z);
			seen[location[z]] = 1;
			last = z;
		}
	}
	a.clear();
	seen.clear();
	for(int y:l)a.push_back({ask(x,y),y});
	sort(a.begin(),a.end());
	last = 0;
	for(auto Z : a){
		int z = Z.second;
		int m = ask(x,last) + ask(last,z);
		m-=ask(x,z);
		m/=2;
		if(location[last] + m <= 1000000 && seen[location[last] + m]){
			stype[z] = 2;
			location[z] = location[last] + ask(last,z);
		}else{
			stype[z] = 1;
			location[z] = location[x] - ask(x,z);
			last = z;
			seen[location[z]] = 1;
			
		}
	}
	
	
	//for(int i=0;i<n;i++)cout<<stype[i]<<" "<<location[i]<<'\n';
}

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