Submission #788128

#	Time	Username	Problem	Language	Result	Execution time	Memory
788128		GusterGoose27	Towns (IOI15_towns)	C++17	25 / 100	13 ms	636 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];
int sz[MAXN];
bool matched[MAXN];
int cache[MAXN][MAXN];
int paired[MAXN];
int diam;
int n;
int amt;

void reset(int sub) {
	if (sub == 1) amt = n*(n-1)/2;
	if (sub == 2) amt = (7*n+1)/2;
	if (sub == 3) amt = n*(n-1)/2;
	if (sub == 4) amt = (7*n+1)/2;
	if (sub == 5) amt = 5*n;
	if (sub == 6) amt = (7*n+1)/2;
	// dist, ignore
	iota(uf, uf+n, 0);
	fill(sz, sz+n, 1);
	fill(matched, matched+n, 0);
	for (int i = 0; i < n; i++) fill(cache[i], cache[i]+n, 0);
	// paired, ignore
}

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;
	sz[i] += sz[j];
}

int getdist(int i, int j) {
	assert(i >= 0 && j >= 0 && i < n && j < n);
	if (i == j) return 0;
	if (cache[i][j] == 0) {
		assert(amt);
		cache[i][j] = getDistance(i, j);
		amt--;
	}
	return cache[i][j];
}

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

bool valid(vector<int> &vals) {
	int m = vals.size();
	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;
				break;
			}
			if (sz[find(vals[i])] > n/2) return 0;
		}
		if (!f) {
			ex = i;
			break;
		}
	}
	if (ex == -1) return 1;
	for (int i = 0; i < m; i++) {
		if (sz[find(ex)] > n/2) return 0;
		if (find(i) == find(ex)) {
			continue;
		}
		assert(matched[i]);
		if (find(paired[i]) == find(ex)) continue;
		if (same(vals[i], vals[ex])) {
			merge(i, ex);
			continue;
		}
	}
	return sz[find(ex)] <= n/2;
}

int hubDistance(int N, int sub) {
	n = N;
	reset(sub);
	int l = 0;
	int d = 0;
	for (int i = 1; i < n; i++) {
		int cur = getdist(0, i);
		if (cur > d) {
			l = i;
			d = cur;
		}
	}
	// assert(getdist(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] = getdist(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] = getdist(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 (sub < 3) return R;
	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[2].size() && (cont[0].size()+cont[1].size() <= cont[2].size()+cont[3].size())) {
		if (cont[3].size() > n/2 || !valid(cont[2])) return -R;
		return R;
	}
	return -R;
}

Compilation message (stderr)

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

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