Submission #1030820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030820		tolbi	Rail (IOI14_rail)	C++17	56 / 100	216 ms	98540 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
map<pair<int,int>,int> mp;
int _dist[5001][5001];
int dist(int a, int b){
	if (_dist[a][b]==-1) _dist[a][b]=getDistance(a,b);
	return _dist[a][b];
}
void findLocation(int N, int first, int location[], int stype[])
{
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j){
			_dist[i][j]=-1;
			if (i==j) _dist[i][j]=0;
		}
	}
	int c = 0, d = 1;
	for (int i = 2; i < N; i++){
		if (dist(c,i)<dist(c,d)) d=i;
	}
	vector<int> left;
	vector<int> right;
	stype[c]=1,stype[d]=2;
	location[c]=first,location[d]=first+dist(c,d);
	for (int i = 0; i < N; i++){
		if (i==c || i==d) continue;
		if (dist(c,i)==dist(c,d)+dist(d,i)){
			if (dist(d,i)<dist(c,d)){
				location[i]=location[d]-dist(d,i);
				stype[i]=1;
			}
			else left.push_back(i);
		}
		else {
			right.push_back(i);
		}
	}
	sort(left.begin(), left.end(), [&](int a, int b){
		return dist(d,a)<dist(d,b);
	});
	sort(right.begin(), right.end(), [&](int a, int b){
		return dist(c,a)<dist(c,b);
	});
	if (left.size()){
		vector<int> virt;
		virt.push_back(left[0]);
		location[virt.back()]=location[d]-dist(d,virt.back());
		stype[virt.back()]=1;
		for (int _ = 1; _ < left.size(); _++){
			int i = left[_];
			bool boolean=false;
			int fiC;
			for (int j = 0; j < virt.size(); j++){
				fiC=virt[j];
				if (dist(d,i)==dist(d,fiC)+dist(fiC,i)){
					boolean=true;
					break;
				}
			}
			if (boolean){
				stype[i]=2;
				location[i]=location[fiC]+dist(fiC,i);
			}
			else {
				stype[i]=1;
				location[i]=location[d]-dist(d,i);
				virt.push_back(i);
			}
		}
	}
	if (right.size()){
		vector<int> virt;
		virt.push_back(right[0]);
		location[virt.back()]=location[c]+dist(c,virt.back());
		stype[virt.back()]=2;
		for (int _ = 1; _ < right.size(); _++){
			int i = right[_];
			bool boolean=false;
			int fiD;
			for (int j = 0; j < virt.size(); j++){
				fiD=virt[j];
				if (dist(c,i)==dist(c,fiD)+dist(fiD,i)){
					boolean=true;
					break;
				}
			}
			if (boolean){
				stype[i]=1;
				location[i]=location[fiD]-dist(fiD,i);
			}
			else {
				stype[i]=2;
				location[i]=location[c]+dist(c,i);
				virt.push_back(i);
			}
		}
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int _ = 1; _ < left.size(); _++){
      |                   ~~^~~~~~~~~~~~~
rail.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for (int j = 0; j < virt.size(); j++){
      |                    ~~^~~~~~~~~~~~~
rail.cpp:78:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for (int _ = 1; _ < right.size(); _++){
      |                   ~~^~~~~~~~~~~~~~
rail.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    for (int j = 0; j < virt.size(); j++){
      |                    ~~^~~~~~~~~~~~~

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