Submission #788102

#	Time	Username	Problem	Language	Result	Execution time	Memory
788102		GusterGoose27	Towns (IOI15_towns)	C++17	13 / 100	12 ms	352 KiB

towns

#include "towns.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 120;
const int inf = 1e9;
int dist[MAXN][2];
int uf[MAXN];
bool matched[MAXN];
int paired[MAXN];
int diam;
int n;

int _abs(int a) {
	return a < 0 ? -a : a;
}

int find(int i) {
	return uf[i] == i ? i : uf[i] = find(uf[i]);
}

void merge(int i, int j) {
	i = find(i);
	j = find(j);
	assert(i != j);
	uf[i] = j;
}

bool same(int i, int j) {
	return dist[i][0]+dist[i][1]+dist[j][0]+dist[j][1] == 2*diam+2*getDistance(i, j);
}

bool valid(vector<int> &vals) {
	int m = vals.size();
	iota(uf, uf+m, 0);
	int ex = -1;
	for (int i = 0; i < m; i++) {
		if (matched[i]) continue;
		bool f = 0;
		for (int _ = i+1; _ < m+i; _++) {
			int j = _%m;
			if (matched[j] || find(i) == find(j)) continue;
			if (same(vals[i], vals[j])) {
				merge(i, j);
			}
			else {
				matched[i] = matched[j] = 1;
				paired[i] = j;
				paired[j] = i;
				f = 1;
			}
		}
		if (!f) {
			ex = i;
			break;
		}
	}
	if (ex == -1) return 1;
	int sz = 0;
	for (int i = 0; i < m; i++) {
		if (find(i) == find(ex)) {
			sz++;
			continue;
		}
		if (find(paired[i]) == find(ex)) continue;
		if (same(vals[i], vals[ex])) {
			merge(i, ex);
			sz++;
			continue;
		}
	}
	return sz <= n/2;
}

int hubDistance(int N, int sub) {
	n = N;
	int l = 0;
	int d = 0;
	for (int i = 1; i < n; i++) {
		int cur = getDistance(0, i);
		if (cur > d) {
			l = i;
			d = cur;
		}
	}
	// assert(getDistance(0, l) == d);
	dist[l][0] = 0;
	dist[0][0] = d;
	int r = 0;
	for (int i = 1; i < n; i++) {
		if (i == l) continue;
		dist[i][0] = getDistance(i, l);
		if (dist[i][0] > dist[r][0]) r = i;
	}
	dist[r][1] = 0;
	for (int i = 0; i < n; i++) {
		if (i == r) continue;
		if (i == l) {
			dist[i][1] = dist[r][0];
			continue;
		}
		dist[i][1] = getDistance(i, r);
	}
	int mn = inf;
	for (int i = 0; i < n; i++) {
		mn = min(mn, _abs(dist[i][0]-dist[i][1]));
	}
	// return (mn+dist[r][0])/2;
	vector<int> cont[4];
	for (int i = 0; i < n; i++) {
		int diff = dist[i][1]-dist[i][0];
		if (diff > mn) cont[0].push_back(i);
		else if (diff == mn) cont[1].push_back(i);
		else if (diff == -mn) cont[2].push_back(i);
		else cont[3].push_back(i);
	}
	diam = dist[l][1];
	int R = (diam+mn)/2;
	if (cont[1].size() && (cont[0].size()+cont[1].size() >= cont[2].size()+cont[3].size())) {
		if (cont[0].size() > n/2 || !valid(cont[1])) return -R;
		return R;
	}
	if (cont[3].size() > n/2 || !valid(cont[2])) return -R;
	return R;
}

Compilation message (stderr)

towns.cpp: In function 'bool valid(std::vector<int>&)':
towns.cpp:36:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   36 |  int m = vals.size();
      |          ~~~~~~~~~^~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:122:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  122 |   if (cont[0].size() > n/2 || !valid(cont[1])) return -R;
      |       ~~~~~~~~~~~~~~~^~~~~
towns.cpp:125:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |  if (cont[3].size() > n/2 || !valid(cont[2])) return -R;
      |      ~~~~~~~~~~~~~~~^~~~~
towns.cpp:77:28: warning: unused parameter 'sub' [-Wunused-parameter]
   77 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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