Submission #417007

#	Time	Username	Problem	Language	Result	Execution time	Memory
417007		vanic	Rail (IOI14_rail)	C++14	56 / 100	485 ms	173816 KiB

rail

#include "rail.h"
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const int maxn=5e3+5;

int dist[maxn][maxn];
int posevi[maxn];
int boje[maxn];

void rijesi(int x, int pos, int boja, vector < int > svi){
	posevi[x]=pos;
	boje[x]=boja;
	if(svi.empty()){
		return;
	}
	int iduc;
	int mini=1e9;
	for(int i=0; i<(int)svi.size(); i++){
		if(mini>dist[x][svi[i]]){
			mini=dist[x][svi[i]];
			iduc=svi[i];
		}
	}
	vector < int > l, d;
	for(int i=0; i<(int)svi.size(); i++){
		if(svi[i]==iduc){
			continue;
		}
		if(dist[iduc][svi[i]]<dist[x][svi[i]]){
			l.push_back(svi[i]);
		}
		else{
			d.push_back(svi[i]);
		}
	}
	rijesi(x, pos, boja, d);
	if(boja==1){
		rijesi(iduc, pos+dist[x][iduc], 2, l);
	}
	else{
		rijesi(iduc, pos-dist[x][iduc], 1, l);
	}
}

void findLocation(int n, int pos, int sol1[], int sol2[]){
	vector < int > svi;
	for(int i=0; i<n; i++){
		if(i){
			svi.push_back(i);
		}
		for(int j=i+1; j<n; j++){
			dist[i][j]=getDistance(i, j);
			dist[j][i]=dist[i][j];
		}
	}
	rijesi(0, pos, 1, svi);
	for(int i=0; i<n; i++){
		sol1[i]=posevi[i];
		sol2[i]=boje[i];
	}
}

Compilation message (stderr)

rail.cpp: In function 'void rijesi(int, int, int, std::vector<int>)':
rail.cpp:42:32: warning: 'iduc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |   rijesi(iduc, pos+dist[x][iduc], 2, l);
      |                    ~~~~~~~~~~~~^

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