Submission #785596

#	Time	Username	Problem	Language	Result	Execution time	Memory
785596		NothingXD	Towns (IOI15_towns)	C++17	26 / 100	17 ms	440 KiB

towns

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << " ";
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 200 + 10;

int n, dis[maxn][maxn];
int par[maxn];

int getpar(int v){
	return (par[v] < 0? v: par[v] = getpar(par[v]));
}

void merge(int u, int v){
	if ((u = getpar(u)) == (v = getpar(v))) return;
	par[v] += par[u];
	par[u] = v;
}

int hubDistance(int N, int sub) {
	n = N;
	for (int i = 0; i < n; i++){
		for (int j = i+1; j < n; j++){
			dis[i][j] = dis[j][i] = getDistance(i, j);
		}
	}
	int r1 = max_element(dis[0], dis[0] + n) - dis[0];
	int r2 = max_element(dis[r1], dis[r1] + n) - dis[r1];
	int ans = dis[r1][r2];
	vector<int> idx;
	for (int i = 0; i < n; i++){
		int tmp = (dis[r1][i] + dis[r1][r2] - dis[r2][i]) / 2;
		int val = max(tmp, dis[r1][r2] - tmp);
		if (val < ans){
			idx.clear();
			ans = val;
		}
		if (val == ans) idx.push_back(tmp);
	}
	sort(all(idx));
	idx.resize(distance(idx.begin(), unique(all(idx))));
	bool flg = false;
	for (auto x: idx){
		int a = 0, b = 0;
		vector<int> ver;
		for (int i = 0; i < n; i++){
			int tmp = (dis[r1][i] + dis[r1][r2] - dis[r2][i]) / 2;
			if (tmp < x) a++;
			else if (tmp > x) b++;
			else ver.push_back(i);
		}
		if (a > n/2 || b > n/2) continue;
		memset(par, -1, sizeof par);
		for (int i = 0; i < ver.size(); i++){
			for (int j = i+1; j < ver.size(); j++){
				if (dis[ver[i]][ver[j]] < dis[r1][ver[i]] + dis[r1][ver[j]] - 2 * x) merge(ver[i], ver[j]);
			}
		}
		bool ok = true;
		for (int i = 0; i < ver.size(); i++){
			if (par[ver[i]] < -(n/2)) ok = false;
		}
		if (ok) flg = true;
	}
	return (flg? ans: -ans);
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:49:43: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   49 |  int r1 = max_element(dis[0], dis[0] + n) - dis[0];
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
towns.cpp:50:45: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   50 |  int r2 = max_element(dis[r1], dis[r1] + n) - dis[r1];
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
towns.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for (int i = 0; i < ver.size(); i++){
      |                   ~~^~~~~~~~~~~~
towns.cpp:77:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |    for (int j = i+1; j < ver.size(); j++){
      |                      ~~^~~~~~~~~~~~
towns.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (int i = 0; i < ver.size(); i++){
      |                   ~~^~~~~~~~~~~~
towns.cpp:42:28: warning: unused parameter 'sub' [-Wunused-parameter]
   42 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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