Submission #902113

#	Time	Username	Problem	Language	Result	Execution time	Memory
902113		UmairAhmadMirza	Rail (IOI14_rail)	C++14	30 / 100	114 ms	1164 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
int const N=5005;
int dist1[N];
int dist2[N];
bool done[N];
int getDistance(int i, int j);
void findLocation(int n, int firloc, int location[], int stype[]){
	int fir=0;
	location[0]=firloc;
	stype[0]=1;
	done[fir]=1;
	if(n==1)
		return;
	set<pair<int,int>> dd;
	for (int i = 1; i < n; ++i){
		dist1[i]=getDistance(0,i);
		dd.insert({dist1[i],i});
	}
	// cout<<endl;
	auto p=*(dd.begin());
	int sec=p.second;
	for (int i = 1; i < n; ++i)
	{
		if(i==sec)
			continue;
		dist2[i]=getDistance(sec,i);
		if(dist2[i]<dist1[i] && dist2[i]>dist1[sec])
			dd.erase({dist1[i],i});
	}
	while(dd.size()){
		auto p=*(dd.begin());
		dd.erase(p);
		int seco=p.second;
		location[seco]=p.first+location[0];
		stype[seco]=2;
		done[seco]=1;
		// cout<<"mini"<<endl;
		// cout<<location[0]<<endl;
		// cout<<seco<<' '<<p.first<<endl;
		for (int i = 1; i < n; ++i)
		{
			if(done[i])
				continue;
			if(dist2[i]<dist1[i] && dist2[i]-dist1[seco]>0)
				continue;
			int dis=getDistance(seco,i);
			if(dist1[i]-dist1[seco]==dis){
				done[i]=1;
				location[i]=location[seco]-dis;
				stype[i]=1;
				dd.erase({dist1[i],i});
			}
		}
	}
	for (int i = 1; i < n; ++i)
		if(done[i]==0)
			dd.insert({dist2[i],i});
	while(dd.size()){
		auto p=*(dd.begin());
		dd.erase(p);
		int firo=p.second;
		location[firo]=location[sec]-p.first;
		stype[firo]=1;
		done[firo]=1;
		for (int i = 1; i < n; ++i)
		{
			if(done[i])
				continue;
			int dis=getDistance(firo,i);
			if(dist2[i]-dist2[firo]==dis){
				done[i]=1;
				location[i]=location[firo]+dis;
				stype[i]=2;
				dd.erase({dist2[i],i});
			}
		}
	}
	// for (int i = 0; i < n; ++i)
	// 	cout<<location[i]<<' '<<stype[i]<<endl;
}

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