Submission #785575

#	Time	Username	Problem	Language	Result	Execution time	Memory
785575		NothingXD	Towns (IOI15_towns)	C++17	0 / 100	1 ms	212 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[2][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++){
		dis[0][i] = getDistance(0, i);
	}
	int r1 = max_element(dis[0], dis[0] + n) - dis[0];
	for (int i = 0; i < n; i++){
		dis[0][i] = getDistance(r1, i);
	}
	int r2 = max_element(dis[0], dis[0] + n) - dis[0];
	for (int i = 0; i < n; i++){
		dis[1][i] = getDistance(r2, i);
	}
	int ans = dis[0][r2];
	vector<int> idx;
	for (int i = 0; i < n; i++){
		int tmp = (dis[0][i] + dis[0][r2] - dis[1][i]) / 2;
		int val = max(tmp, dis[0][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[0][i] + dis[0][r2] - dis[1][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++){
				int tmp = getDistance(ver[i], ver[j]);
				if (tmp < dis[0][ver[i]] + dis[0][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;
	}
	if (sub <= 2) return ans;
	return (flg? ans: -ans);
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:47:43: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   47 |  int r1 = max_element(dis[0], dis[0] + n) - dis[0];
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
towns.cpp:51:43: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   51 |  int r2 = max_element(dis[0], dis[0] + n) - dis[0];
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
towns.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int i = 0; i < ver.size(); i++){
      |                   ~~^~~~~~~~~~~~
towns.cpp:81:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |    for (int j = i+1; j < ver.size(); j++){
      |                      ~~^~~~~~~~~~~~
towns.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for (int i = 0; i < ver.size(); i++){
      |                   ~~^~~~~~~~~~~~

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