Submission #750639

#	Time	Username	Problem	Language	Result	Execution time	Memory
750639		Abrar_Al_Samit	Rail (IOI14_rail)	C++17	56 / 100	989 ms	98508 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

const int nax = 5000;

int mem[nax][nax];
int know[nax];
bool direct[nax];

int get(int a, int b) {
	assert(a!=b);
	if(mem[a][b]) return mem[a][b];

	return mem[a][b] = mem[b][a] = getDistance(a, b);
}

void solve(int N, int leftMost, int location[], int stype[]) {
	cerr<<leftMost<<' '<<location[leftMost]<<'\n';

	while(1) {
		bool yes = false;
		for(int i=0; i<N; ++i) {
			if(!know[i]) yes = true;
		}
		if(!yes) break;

		int ndt;
		int dis = 1e9;
		for(int i=0; i<N; ++i) if(!know[i])  {
			if(dis>get(leftMost, i)) {
				dis = get(leftMost, i);
				ndt = i;
			}
		}

		location[ndt] = location[leftMost] + dis;
		stype[ndt] = 2;
		know[ndt] = 1;

		for(int i=0; i<N; ++i) if(!know[i]) {
			int d1 = get(leftMost, ndt);
			int d2 = get(ndt, i);

			if(get(leftMost, i)==d1+d2) {
				know[i] = 1;
				location[i] = location[ndt] - d2;
				stype[i] = 1;
			}
		}
	}

	for(int i=0; i<N; ++i) {
		cerr<<location[i]<<' '<<stype[i]<<'\n';
	}
}
void findLocation(int N, int first, int location[], int stype[]) {
	location[0] = first, stype[0] = 1;
	if(N==1) return;

	know[0] = 1;

	int ndt;
	int dis = 1e9;
	for(int i=1; i<N; ++i) {
		if(get(0, i)<dis) {
			dis = get(0, i);
			ndt = i;
		}
	}
	location[ndt] = first + dis, stype[ndt] = 2;
	know[ndt] = 1;


	for(int i=0; i<N; ++i) {
		direct[i] = 1;
	}
	for(int i=0; i<N; ++i) {
		for(int j=0; j<N; ++j) if(i!=j) {
			if(i!=ndt && j!=ndt) {
				int d1 = get(i, ndt);
				int d2 = get(j, ndt);

				if(get(i, j)==d1-d2) {
					direct[i] = 0;
				}
			}
		}
	}


	int vf = 0, loc = first;

	for(int i=1; i<N; ++i) {
		if(i==ndt) continue;
		if(!direct[i]) continue;

		int d1 = get(0, i);
		int d2 = get(ndt, i);

		if(d1==get(0, ndt)+d2) {
			if(location[ndt]-d2<loc) {
				vf = i;
				loc = location[ndt]-d2;
			}
		}
	}

	know[0] = know[ndt] = 0;

	location[vf] = loc;
	stype[vf] = 1;
	know[vf] = 1;
	solve(N, vf, location, stype);
}

Compilation message (stderr)

rail.cpp: In function 'void solve(int, int, int*, int*)':
rail.cpp:43:16: warning: 'ndt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |    int d2 = get(ndt, i);
      |             ~~~^~~~~~~~
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:71:11: warning: 'ndt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |  location[ndt] = first + dis, stype[ndt] = 2;
      |           ^~~

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