Submission #794738

#	Time	Username	Problem	Language	Result	Execution time	Memory
794738		fatemetmhr	Towns (IOI15_towns)	C++17	100 / 100	14 ms	1108 KiB

towns

//  ~ Be Name Khoda ~  //

#include "towns.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  200;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;


ll keep[maxn5][maxn5];
ll len[maxn5];
int n;
vector <int> av, tng, mesl;

ll gdis(int a, int b){
	if(a == b)
		return 0;
	if(keep[a][b] != -1)
		return keep[a][b];
	return keep[a][b] = keep[b][a] = getDistance(a, b);
}

bool iden(int a, int b){
	return len[a] + len[b] != gdis(a, b);
}

bool cent(int a, ll R){
	bool found = false;
	av.clear();
	tng.clear();
	mesl.clear();
	for(int i = 0; i < n; i++)
		found |= (gdis(a, i) - len[i] == R);
	//cout << a << ' ' << b << ' ' << R << ' ' << found << endl;
	if(!found)
		return false;
	int num0 = 0, num1 = 0;
	for(int i = 0; i < n; i++){
		if(gdis(i, a) - len[i] < R)
			num0++;
		if(gdis(i, a) - len[i] > R)
			num1++;
		if(gdis(i, a) - len[i] == R)
			av.pb(i);
	}
	//cout << num0 << ' ' << num1 << ' ' << av.size() << endl;
	if(max(num0, num1) > n / 2)
		return false;
	if(av.size() <= n / 2)
		return true;
	for(int i = 1; i < av.size(); i += 2){
		if(iden(av[i], av[i - 1]))
			mesl.pb(av[i]);
		else{
			tng.pb(av[i]);
			tng.pb(av[i - 1]);
		}
	}
	int cnt = 0, id = -1;
	for(auto x : mesl){
		if(cnt == 0){
			cnt = 2;
			id = x;
			continue;
		}
		if(iden(x, id))
			cnt += 2;
		else{
			cnt -= 2;
			if(cnt == -1){
				cnt = 1;
				id = x;
			}
		}
	}
	if(int(av.size()) & 1){
		if(cnt == 0)
			id = av.back();
		else if(!iden(av.back(), id))
			cnt--;
	}
	if(cnt == 0 || id == -1)
		return true;
	cnt = 0;
	for(auto u : mesl) if(iden(u, id))
		cnt += 2;
	for(auto u : tng) if(iden(u, id))
		cnt++;
	if(int(av.size()) & 1)
		if(iden(id, av.back()))
			cnt++;
	//cout << "haaaa " << cnt << ' ' << id << endl;
	return cnt <= n / 2;
}

int hubDistance(int N, int sub){
	n = N;
	memset(keep, -1, sizeof keep);
	int dim1 = 0, dim2 = 1;
	int v = 0, u = 1;
	for(int i = 2; i < n; i++) if(gdis(v, u) < gdis(v, i))
		u = i;
	ll tR = 0;
	for(int i = 0; i < n; i++){
		tR = max(tR, gdis(i, u));
		len[i] = (gdis(i, u) + gdis(i, v) - gdis(u, v)) / 2;
	}

	ll R = tR;
	for(int i = 0; i < n; i++)
		R = min(R, max(gdis(i, u) - len[i], tR - (gdis(i, u) - len[i])));

	if(cent(u, R))
		return R;
	if(cent(u, tR - R))
		return R;
	return -R;
}

Compilation message (stderr)

towns.cpp: In function 'bool cent(int, ll)':
towns.cpp:69:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |  if(av.size() <= n / 2)
      |     ~~~~~~~~~~^~~~~~~~
towns.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i = 1; i < av.size(); i += 2){
      |                 ~~^~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:134:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  134 |   return R;
      |          ^
towns.cpp:136:10: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  136 |   return R;
      |          ^
towns.cpp:137:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  137 |  return -R;
      |         ^~
towns.cpp:119:6: warning: unused variable 'dim1' [-Wunused-variable]
  119 |  int dim1 = 0, dim2 = 1;
      |      ^~~~
towns.cpp:119:16: warning: unused variable 'dim2' [-Wunused-variable]
  119 |  int dim1 = 0, dim2 = 1;
      |                ^~~~
towns.cpp:116:28: warning: unused parameter 'sub' [-Wunused-parameter]
  116 | 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