Submission #115631

#	Time	Username	Problem	Language	Result	Execution time	Memory
115631		E869120	Towns (IOI15_towns)	C++14	35 / 100	19 ms	640 KiB

towns

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

int N, dist[183][179];

int getdist(int u, int v) {
	if (u == v) return 0;
	if (dist[u][v] >= 1) return dist[u][v] - 1;
	
	int R = getDistance(u, v);
	dist[u][v] = R + 1; dist[v][u] = R + 1;
	return R;
}

pair<int, int> Furthest(int pos) {
	int maxn = -1, maxid = -1;
	for (int i = 0; i < N; i++) {
		int D = getdist(pos, i);
		if (D > maxn) { maxn = D; maxid = i; }
	}
	return make_pair(maxn, maxid);
}

int hubDistance(int NN, int sub) {
	for (int i = 0; i < NN * NN; i++) dist[i / NN][i % NN] = 0;
	N = NN;
	pair<int, int> E1 = Furthest(0);
	pair<int, int> E2 = Furthest(E1.second);
	
	int diameter = E2.first, u1 = E1.second, u2 = E2.second, minx = (1 << 30);
	for (int i = 0; i < N; i++) {
		minx = min(minx, abs(getdist(u1, i) - getdist(u2, i)));
	}
	
	int t[4] = {0, 0, 0, 0};
	for (int i = 0; i < N; i++) {
		int V1 = getdist(u1, i);
		int V2 = getdist(u2, i);
		if (V1 < V2) {
			if (abs(V1 - V2) == minx) t[1]++;
			else t[0]++;
		}
		if (V1 >= V2) {
			if (abs(V1 - V2) == minx) t[2]++;
			else t[3]++;
		}
	}
	
	bool flag = false;
	if (t[1] >= 1 && max({t[0], t[1], t[2] + t[3]}) <= N / 2) flag = true;
	if (t[2] >= 1 && max({t[0] + t[1], t[2], t[3]}) <= N / 2) flag = true;
	if (flag == true) return (diameter + minx) / 2;
	return -1 * ((diameter + minx) / 2);
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:25:29: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int NN, int sub) {
                             ^~~

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