Submission #550804

#	Time	Username	Problem	Language	Result	Execution time	Memory
550804		CSQ31	Rail (IOI14_rail)	C++17	30 / 100	91 ms	54392 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;
	for(auto Z : a){
		int z = Z.second;
		//case 1 d(y,z) > d(0,z)
		//case 2 d(y,z) < d(0,z);
		if(ask(last,z) > ask(0,z)){ //type D
			stype[z] = 2;
			location[z] = location[0] + ask(0,z);
			last = z;
		}else{ //type C
			stype[z] = 1;
			location[z] = location[last] - ask(last,z);
		}
	}
	//solving for left side is symmetric
	a.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;
		//case 1 d(y,z) > d(x,z)
		//case 2 d(y,z) < d(x,z);
		if(ask(last,z) > ask(x,z)){ //type c
			stype[z] = 1;
			location[z] = location[x] - ask(x,z);
			last = z;
		}else{
			stype[z] = 2;
			location[z] = location[last] + ask(last,z);
		}
	}
	//for(int i=0;i<n;i++)cout<<stype[i]<<" "<<location[i]<<'\n';
}

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