제출 #383867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383867		LucaDantas	Towns (IOI15_towns)	C++17	0 / 100	25 ms	748 KiB

towns

#include "towns.h"
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <vector>
#include <map>
 
constexpr int maxn = 300;
 
int dp[maxn][maxn];//, c[maxn];
 
std::map<int, int> filhos;
// std::map<int, std::vector<int>> filhos;
 
int get(int i, int j) {
	if(i > j) std::swap(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) {
	memset(dp, -1, sizeof dp);
	// memset(c, 0, sizeof c);
	filhos.clear();
	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);
		int c = (d1 + d2 - dist) >> 1;
		// c[i] = (d1 + d2 - dist) >> 1;
		R = min(R, max(d1, d2) - c);
		// R = min(R, max(d1, d2) - c[i]);
		filhos[d1-c]++;
	}
	// if(sub <= 2) return R;
	// if(sub != 4) assert(0);
	int sz = 1;
	bool ok = 0;
	for(auto it : filhos) {
		printf("%d %d\n", it.first, it.second);
		if(it.first == R || it.first == dist - R) {
			if(sz <= (N >> 1) && N - sz - it.second <= (N >> 1)
			&& it.second <= (N >> 1)) ok = 1;
			puts("A");
		}
		sz += it.second;
	}
	return R * (ok?1:-1);
}

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:24:28: warning: unused parameter 'sub' [-Wunused-parameter]
   24 | 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