Submission #790245

#	Time	Username	Problem	Language	Result	Execution time	Memory
790245		Sohsoh84	Towns (IOI15_towns)	C++17	0 / 100	11 ms	356 KiB

towns

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

using namespace std;

typedef pair<int, int> pll;

#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 300 + 10;

int n, D0[MAXN], D1[MAXN], diam, diam_v, diam_u;

inline int get(int u, int v) {
	return getDistance(u, v);
}

inline int mirror_on_0u(int v) {
	return (D1[v] - D0[v] + D0[diam_u]) / 2;
}

int hubDistance(int N_, int sub) {
	memset(D0, 0, sizeof D0);
	memset(D1, 0, sizeof D1);

	n = N_;
	for (int i = 1; i < n; i++)
		D0[i] = get(0, i);

	map<int, int> mp;

	diam_u = max_element(D0, D0 + n) - D0;
	D1[0] = D0[diam_u];
	for (int i = 1; i < n; i++) {
		if (i == diam_u) continue;
		D1[i] = get(diam_u, i);
	}

	diam_v = max_element(D1, D1 + n) - D1;
	diam = D1[diam_v];

	int v_mir = mirror_on_0u(diam_v), r = numeric_limits<int>::max();
	vector<int> cent;
	for (int i = 0; i < n; i++) {
		if (mirror_on_0u(i) > v_mir) continue;
		int a = mirror_on_0u(i);
		int b = v_mir - mirror_on_0u(i) + (D1[diam_v] - mirror_on_0u(i));

		int tr = max(a, b);
		if (tr < r) {
			cent.clear();
			cent.push_back(a);
			r = tr;
		} else if (tr == r) cent.push_back(a);
	}
	
	
	return r;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:35:35: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   35 |  diam_u = max_element(D0, D0 + n) - D0;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:42:35: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   42 |  diam_v = max_element(D1, D1 + n) - D1;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:25:29: warning: unused parameter 'sub' [-Wunused-parameter]
   25 | 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