Submission #434591

#	Time	Username	Problem	Language	Result	Execution time	Memory
434591		Tangent	Towns (IOI15_towns)	C++17	0 / 100	256 ms	396 KiB

towns

#include "towns.h"
#include "bits/stdc++.h"
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
 
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()

map<pii, int> memo;
vvii dist2;
int dist(int u, int v) {
	// if (!memo[{u, v}]) {
	// 	memo[{u, v}] = memo[{v, u}] = getDistance(u, v);
	// }
	return dist2[u][v];
}

int hubDistance(int n, int sub) {
	int res = 1000000000;
	// vector<map<int, int>> hubds(n);
	// vvii hubs;
	dist2.assign(n, vii(n));
	rep(i, n - 1) {
		ffor(j, i + 1, n) {
			dist2[i][j] = dist2[j][i] = getDistance(i, j);
		}
	}
	rep(i, n - 1) {
		ffor(j, i + 1, n) {
			map<int, int> xs;
			rep(k, n) {
				if (k == i || k == j) {
					continue;
				}
				int a = dist(i, j), b = dist(j, k), c = dist(i, k);
				int x = (a + c - b) / 2, y = (a + b - c) / 2, z = (b + c - a) / 2;
				// int hub;
				// if (hubds[i].find(x) != hubds[i].end()) {
				// 	hub = hubds[i][x];
				// } else if (hubds[j].find(y) != hubds[j].end()) {
				// 	hub = hubds[j][y];
				// } else if (hubds[k].find(z) != hubds[k].end()) {
				// 	hub = hubds[k][z];
				// } else {
				// 	hub = hubs.size();
				// 	hubs.emplace_back(vii(n));
				// }
				// hubds[i][x] = hubds[j][y] = hubds[k][z] = hub;
				// hubs[hub][i] = x;
				// hubs[hub][j] = y;
				// hubs[hub][k] = z;
				xs[x] = max(xs[x], max(x, max(y, z)));
			}
			forin(p, xs) {
				int curr = p.second;
				forin(p2, xs) {
					if (p != p2) {
						curr = max(curr, abs(p2.first - p.first) + p2.second);
					}
				}
				res = min(res, curr);
			}
		}
	}
	// forin(hub, hubs) {
	// 	res = min(res, *max_element(all(hub)));
	// }
	return res;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:40:44: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   40 |    dist2[i][j] = dist2[j][i] = getDistance(i, j);
      |                                            ^
towns.cpp:40:47: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   40 |    dist2[i][j] = dist2[j][i] = getDistance(i, j);
      |                                               ^
towns.cpp:50:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   50 |     int a = dist(i, j), b = dist(j, k), c = dist(i, k);
      |                  ^
towns.cpp:50:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   50 |     int a = dist(i, j), b = dist(j, k), c = dist(i, k);
      |                     ^
towns.cpp:50:34: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   50 |     int a = dist(i, j), b = dist(j, k), c = dist(i, k);
      |                                  ^
towns.cpp:50:37: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   50 |     int a = dist(i, j), b = dist(j, k), c = dist(i, k);
      |                                     ^
towns.cpp:50:50: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   50 |     int a = dist(i, j), b = dist(j, k), c = dist(i, k);
      |                                                  ^
towns.cpp:50:53: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   50 |     int a = dist(i, j), b = dist(j, k), c = dist(i, k);
      |                                                     ^
towns.cpp:33:28: warning: unused parameter 'sub' [-Wunused-parameter]
   33 | 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