oj.uz

Submission #434677

# Submission time Handle Problem Language Result Execution time Memory
434677 2021-06-21T14:34:22 Z Tangent Towns (IOI15_towns) C++17
25 / 100
 24 ms 864 KB 
#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;
int dist(int u, int v) {
	if (!memo[{u, v}]) {
		memo[{u, v}] = memo[{v, u}] = getDistance(u, v);
	}
	return memo[{u, v}];
}

int hubDistance(int n, int sub) {
	int res = 1000000000;
	memo.clear();
	
	int furthest = 1, maxdist = dist(0, 1);
	ffor(i, 2, n) {
		if (dist(0, i) > maxdist) {
			maxdist = dist(0, i);
			furthest = i;
		}
	}
	int furthest2 = 0;
	maxdist = dist(furthest, 0);
	ffor(i, 1, n) {
		if (i != furthest && dist(furthest, i) > maxdist) {
			maxdist = dist(furthest, i);
			furthest2 = i;
		}
	}

	map<int, int> xs;
	rep(j, n) {
		if (j == furthest || j == furthest2) {
			continue;
		}
		int a = dist(furthest, furthest2), b = dist(furthest2, j), c = dist(furthest, j);
		int x = (a + c - b) / 2, y = (b + c - a) / 2;
		xs[x] = max(xs[x], y);
	}
	forin(p, xs) {
		int curr = max(max(p.second, p.first), dist(furthest, furthest2) - p.first);
		forin(p2, xs) {
			if (p != p2) {
				curr = max(curr, abs(p2.first - p.first) + p2.second);
			}
		}
		res = min(res, curr);
	}

	return res;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:38:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   38 |   if (dist(0, i) > maxdist) {
      |               ^
towns.cpp:39:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   39 |    maxdist = dist(0, i);
      |                      ^
towns.cpp:40:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   40 |    furthest = i;
      |               ^
towns.cpp:46:39: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   46 |   if (i != furthest && dist(furthest, i) > maxdist) {
      |                                       ^
towns.cpp:47:29: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   47 |    maxdist = dist(furthest, i);
      |                             ^
towns.cpp:48:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   48 |    furthest2 = i;
      |                ^
towns.cpp:57:58: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   57 |   int a = dist(furthest, furthest2), b = dist(furthest2, j), c = dist(furthest, j);
      |                                                          ^
towns.cpp:57:81: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   57 |   int a = dist(furthest, furthest2), b = dist(furthest2, j), c = dist(furthest, j);
      |                                                                                 ^
towns.cpp:32:28: warning: unused parameter 'sub' [-Wunused-parameter]
   32 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 332 KB Output is correct
2 Correct 15 ms 372 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 22 ms 492 KB Output is correct
5 Correct 21 ms 496 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 332 KB Output is correct
2 Correct 15 ms 372 KB Output is correct
3 Correct 20 ms 864 KB Output is correct
4 Correct 20 ms 860 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 332 KB Output isn't correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -