Submission #790250

#	Time	Username	Problem	Language	Result	Execution time	Memory
790250		ymm	Towns (IOI15_towns)	C++17	100 / 100	13 ms	852 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;

const int N = 120;
int dis0[N], disa[N];//, disb[N];

int dis[N][N];
int cnt;

namespace dsu {
	int par[N];
	int sz[N];
	void init() {
		fill(par, par+N, -1);
		fill(sz, sz+N, 1);
	}
	int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
	void unite(int v, int u) {
		//v = rt(v);
		//u = rt(u);
		//if (sz[v] < sz[u])
		//	swap(v, u);
		sz[v] += sz[u];
		par[u] = v;
	}
}

int get(int i, int j)
{
	if (i == j)
		return 0;
	if (i > j)
		swap(i, j);
	if (!dis[i][j]) {
		++cnt;
		dis[i][j] = getDistance(i, j);
	}
	return dis[i][j];
}

int get2(int a, int v, int b)
{
	return (get(a, v) + get(a, b) - get(v, b))/2;
}

int find_hub(int a, int b, int n, int r)
{
	if (get(a, b) == r*2)
		return r;
	bool x = 0, y = 0;
	vector<int> X, Y;
	Loop (i,0,n) {
		if (get2(a, i, 0) == r)
			x = 1;
		if (get2(a, i, 0) == get(a, b) - r)
			y = 1;
		int x = get2(a, i, 0);
		int y = get(a, b) - x;
		(x < y? Y: X).push_back(i);
	}
	if (!x)
		return get(a, b) - r;
	if (!y)
		return r;
	if (X.size()*2 > n)
		return r;
	if (X.size()*2 == n)
		return -1;
	return get(a, b) - r;
}

int hubDistance(int n, int sub) {
	memset(dis, 0, sizeof(dis));
	cnt = 0;
	Loop (i,0,n)
		dis0[i] = get(0, i);
	int a = max_element(dis0, dis0+n) - dis0;
	Loop (i,0,n)
		disa[i] = get(a, i);
	int b = max_element(disa, disa+n) - disa;
	//Loop (i,0,n)
	//	disb[i] = get(b, i);
	int ans = 1e9;
	Loop (i,0,n) {
		int x = get2(a, i, 0);
		int y = disa[b] - x;
		ans = min(ans, max(x, y));
	}
	int v = find_hub(a, b, n, ans);
	if (v == -1)
		return ans;
	vector<int> L, M, R;
	Loop (i,0,n) {
		(get2(a, i, 0) < v? L:
		 get2(a, i, 0) > v? R:
		                    M).push_back(i);
	}
	if (L.size()*2 > n || R.size()*2 > n)
		return -ans;
	if (M.size()*2 <= n)
		return ans;
	auto same = [&](int i, int j) {
		return get2(i, a, 0) + get2(j, a, 0) != get(i, j);
	};
	vector<int> M1, M2, M2h;
	for (int i = 0; i < M.size(); i += 2) {
		if (i+1 == M.size()) {
			M2.push_back(M[i]);
		} else if (same(M[i], M[i+1])) {
			M2.push_back(M[i]);
			M2.push_back(M[i+1]);
		} else {
			M1.push_back(M[i]);
			M1.push_back(M[i+1]);
		}
	}
	int x = -1, cnt = 0;
	for (int i = 0; i < M2.size(); i += 2) {
		int z = M2[i];
		if (cnt == 0 || same(x, z)) {
			x = z;
			++cnt;
		} else {
			--cnt;
		}
	}
	if (cnt == 0)
		return ans;
	cnt = 0;
	for (int i = 0; i < M2.size(); i += 2) {
		if (same(M2[i], x)) {
			++cnt;
			if (i+1 < M2.size())
				++cnt;
		}
	}
	if (cnt*2 <= M2.size())
		return ans;
	for (int y : M1)
		cnt += same(x, y);
	if (cnt*2 <= n)
		return ans;
	return -ans;
}

Compilation message (stderr)

towns.cpp: In function 'int find_hub(int, int, int, int)':
towns.cpp:58:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   58 |   if (get2(a, i, 0) == r)
      |               ^
towns.cpp:60:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   60 |   if (get2(a, i, 0) == get(a, b) - r)
      |               ^
towns.cpp:62:7: warning: declaration of 'x' shadows a previous local [-Wshadow]
   62 |   int x = get2(a, i, 0);
      |       ^
towns.cpp:55:7: note: shadowed declaration is here
   55 |  bool x = 0, y = 0;
      |       ^
towns.cpp:62:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   62 |   int x = get2(a, i, 0);
      |                   ^
towns.cpp:63:7: warning: declaration of 'y' shadows a previous local [-Wshadow]
   63 |   int y = get(a, b) - x;
      |       ^
towns.cpp:55:14: note: shadowed declaration is here
   55 |  bool x = 0, y = 0;
      |              ^
towns.cpp:64:27: warning: conversion from 'll' {aka 'long long int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
   64 |   (x < y? Y: X).push_back(i);
      |                           ^
towns.cpp:70:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |  if (X.size()*2 > n)
      |      ~~~~~~~~~~~^~~
towns.cpp:72:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |  if (X.size()*2 == n)
      |      ~~~~~~~~~~~^~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:81:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   81 |   dis0[i] = get(0, i);
      |                    ^
towns.cpp:82:36: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   82 |  int a = max_element(dis0, dis0+n) - dis0;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:84:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   84 |   disa[i] = get(a, i);
      |                    ^
towns.cpp:85:36: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   85 |  int b = max_element(disa, disa+n) - disa;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:90:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   90 |   int x = get2(a, i, 0);
      |                   ^
towns.cpp:99:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   99 |   (get2(a, i, 0) < v? L:
      |            ^
towns.cpp:100:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  100 |    get2(a, i, 0) > v? R:
      |            ^
towns.cpp:101:36: warning: conversion from 'll' {aka 'long long int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
  101 |                       M).push_back(i);
      |                                    ^
towns.cpp:103:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |  if (L.size()*2 > n || R.size()*2 > n)
      |      ~~~~~~~~~~~^~~
towns.cpp:103:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |  if (L.size()*2 > n || R.size()*2 > n)
      |                        ~~~~~~~~~~~^~~
towns.cpp:105:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |  if (M.size()*2 <= n)
      |      ~~~~~~~~~~~^~~~
towns.cpp:111:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for (int i = 0; i < M.size(); i += 2) {
      |                  ~~^~~~~~~~~~
towns.cpp:112:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   if (i+1 == M.size()) {
      |       ~~~~^~~~~~~~~~~
towns.cpp:122:14: warning: declaration of 'cnt' shadows a global declaration [-Wshadow]
  122 |  int x = -1, cnt = 0;
      |              ^~~
towns.cpp:13:5: note: shadowed declaration is here
   13 | int cnt;
      |     ^~~
towns.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |  for (int i = 0; i < M2.size(); i += 2) {
      |                  ~~^~~~~~~~~~~
towns.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |  for (int i = 0; i < M2.size(); i += 2) {
      |                  ~~^~~~~~~~~~~
towns.cpp:138:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |    if (i+1 < M2.size())
      |        ~~~~^~~~~~~~~~~
towns.cpp:142:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |  if (cnt*2 <= M2.size())
      |      ~~~~~~^~~~~~~~~~~~
towns.cpp:77:28: warning: unused parameter 'sub' [-Wunused-parameter]
   77 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~

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