Submission #383760

#	Time	Username	Problem	Language	Result	Execution time	Memory
383760		LucaDantas	도시들 (IOI15_towns)	C++17	25 / 100	21 ms	364 KiB

towns

// Genius moves by me, create the dp function just not to use it
#include "towns.h"
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cassert>

constexpr int maxn = 120;

int dp[maxn][maxn], n, cnt = 0;

int get(int i, int j) {
	if(i > j) std::swap(i, j);
	if(dp[i][j] != -1) return dp[i][j];
	return dp[i][j] != -1 ? dp[i][j] : dp[i][j] = getDistance(i, j);
}

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

int hubDistance(int N, int sub) {
	if(sub > 2) return 0;
	n = N;
	memset(dp, -1, sizeof dp);
	int a = 0, b = 0, dist = 0;
	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < N; j++) {
			if(a != j) {
				int v = get(a, j);
				if(v > dist) b = j, dist = v;
			}
		}
		if(!i) a = b, dist = 0, b = 0;
	}
	int R = 0x3f3f3f3f;
	for(int i = 0; i < N; i++) {
		if(i == a || i == b) continue;
		int d1 = get(a, i), d2 = get(b, i), c = (d1 + d2 - dist) >> 1;
		R = min(R, max(d1, d2) - c);
	}
	return R;
}

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