Submission #599360

#	Time	Username	Problem	Language	Result	Execution time	Memory
599360		Temmie	Towns (IOI15_towns)	C++17	25 / 100	16 ms	348 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>

int hubDistance(int n, int sub) {
	int l1, l2;
	int mx = 0;
	for (int i = 1; i < n; i++) {
		int val = getDistance(0, i);
		if (val > mx) {
			mx = val;
			l1 = i;
		}
	}
	std::vector <int> dl1(n, -1);
	std::vector <int> dl2(n, -1);
	mx = 0;
	for (int i = 0; i < n; i++) {
		if (i == l1) {
			continue;
		}
		dl1[i] = getDistance(l1, i);
		if (dl1[i] > mx) {
			mx = dl1[i];
			l2 = i;
		}
	}
	for (int i = 0; i < n; i++) {
		if (i == l2) {
			continue;
		}
		dl2[i] = getDistance(l2, i);
	}
	int r = 1 << 30;
	for (int i = 0; i < n; i++) {
		if (i == l1 || i == l2) {
			continue;
		}
		//int to = (dl1[i] + dl2[i] - dl1[l2]) / 2;
		int x = (dl1[l2] + dl1[i] - dl2[i]) / 2;
		int y = (dl2[l1] + dl2[i] - dl1[i]) / 2;
		r = std::min(r, std::max(x, y));
	}
	return r;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:4:28: warning: unused parameter 'sub' [-Wunused-parameter]
    4 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~
towns.cpp:35:20: warning: 'l2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |   if (i == l1 || i == l2) {
      |                  ~~^~~~~
towns.cpp:21:23: warning: 'l1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |   dl1[i] = getDistance(l1, i);
      |            ~~~~~~~~~~~^~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39