Submission #1088713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088713		gustavo_d	Towns (IOI15_towns)	C++17	0 / 100	9 ms	604 KiB

towns

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

int hubDistance(int N, int sub) {
	int dist[N][N];
	for (int i=0; i<N; i++) {
		dist[i][i] = 0;
		for (int j=i+1; j<N; j++) {
			dist[i][j] = getDistance(i, j);
			dist[j][i] = dist[i][j];
		}
	}

	int a=0, b=0; int mx=0;
	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++) {
			if (dist[i][j] >= mx) {
				mx = dist[i][j];
				a = i; b = j;
			}
		}
	}
	// cout << a << ' ' << b << endl;

	int R = 1e9;
	for (int c=b+1; c<N; c++) {
		if (a != c and b != c) {
			int d_top_a = (dist[a][c] + dist[a][b] - dist[b][c]) / 2;
			int d_top_b = (dist[b][c] + dist[a][b] - dist[a][c]) / 2;
			if (R > max(d_top_a, d_top_b)) {
				R = max(d_top_a, d_top_b);
			}
		}
	}
	// vector<int> dist_pai(N, 1e9);
	// for (int pivot=0; pivot<N; pivot++) {
	// 	for (int a=0; a<N; a++) {
	// 		for (int b=0; b<N; b++) {
	// 			if (a == pivot or b == pivot or a == b) continue;
	// 			int dist_b_pai = (dist[pivot][b] - dist[pivot][a] + dist[a][b])/2;
	// 			dist_pai[b] = min(dist_b_pai, dist_pai[b]);
	// 		}
	// 	}
	// }

	// vector<vector<int>> dists_from_pai(N, vector<int> (N, 0));
	// for (int b=0; b<N; b++) {
	// 	for (int a=0; a<N; a++) {
	// 		if (a == b) continue;
	// 		dists_from_pai[b][a] = dist[a][b] - dist_pai[b];
	// 	}
	// }

	// int R = 1e9;
	// vector<bool> mark_pai(N, false);
	// for (int a=0; a<N: a++) {
	// 	if (mark_pai[a]) continue;
	// 	vector<int> componente(1, a);
	// 	int r = 0;
	// 	for (int b=a+1; b<N; b++) {
	// 		bool diff = false; // check if pai[a] == pai[b]
	// 		for (int i=0; i<N; i++) {
	// 			if (i == a or i == b) continue;
	// 			if (dists_from_pai[a][i] != dists_from_pai[b][i]) diff = true;
	// 		}
	// 		if (diff) continue;
	// 		componente.push_back(b);
	// 	}
	// 	for (int i=0; i<N; i++) {
	// 		if (i == a) continue;
	// 		r = max(r, dists_from_pai[]);
	// 	}
	// 	R = min(R, r);
	// }
	return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:5:28: warning: unused parameter 'sub' [-Wunused-parameter]
    5 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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