Submission #542607

#	Time	Username	Problem	Language	Result	Execution time	Memory
542607		hollwo_pelw	Towns (IOI15_towns)	C++17	25 / 100	15 ms	1108 KiB

towns

#include "towns.h"

#include <bits/stdc++.h>
using namespace std;

namespace {

const int MAXN = 1 << 8;

struct query_dist {

	int d[MAXN][MAXN];

	inline void clear() {
		memset(d, -1, sizeof d);
		for (int i = 0; i < MAXN; i++)
			d[i][i] = 0;
	}

	inline int operator () (int x, int y) {
		if (d[x][y] == -1)
			d[x][y] = d[y][x] = getDistance(x, y);
		return d[x][y];
	}

} dist;

int hs[MAXN], ht[MAXN], cand[MAXN], pos[MAXN];

inline int same_branch(int u, int v) {
	if (pos[u] != pos[v] || cand[u] != cand[v]) return 0;
	// call at most (N + 1) / 2 times
	return (hs[u] + hs[v] - dist(u, v)) > (pos[u] << 1);
}

bool check(int N) {
	if (count(cand, cand + N, 1) == 0)
		return 0;

	vector<pair<int, int>> v;
	vector<int> st(1, 0);
	int cnt = 1;

	for (int i = 1; i < N; i++) {
		if (st.empty() || same_branch(st.back(), i)) {
			st.push_back(i);
			cnt ++;
		} else {
			int last = st.back();
			st.pop_back();

			v.emplace_back(i, 1);

			if (st.empty()) { // not dominator any more ?
				v.emplace_back(last, cnt);
				cnt = 0;
			}

		}
	}

	if (st.empty()) return 1; // no dominator

	int dominator = st.back();

	for (auto vp : v) {
		if (same_branch(vp.first, dominator))
			cnt += vp.second;
	}

	return cnt <= N / 2;
}

}

int hubDistance(int N, int sub) {
	dist.clear();

	for (int i = 0; i < N; i++)
		hs[i] = dist(0, i);

	int s = max_element(hs, hs + N) - hs;

	for (int i = 0; i < N; i++)
		hs[i] = dist(s, i);

	int t = max_element(hs, hs + N) - hs;

	for (int i = 0; i < N; i++)
		ht[i] = dist(t, i);

	const int diameter = dist(s, t);

	map<int, vector<int>> grp;

	int R = 1e9, last = 0;

	for (int i = 0; i < N; i++) {
		int p = (hs[i] - ht[i] + diameter) >> 1;

		pos[i] = p;
		grp[p].push_back(i);

		R = min(R, max(p, diameter - p));
	}

	if (sub <= 2) return R;

	memset(cand, 0, sizeof cand);

	int mn = 1e9;

	for (auto vp : grp) {
		vector<int> v = vp.second;
		int p = vp.first, n = v.size();

		if (max(p, diameter - p) == R && max(last, N - n - last) <= N / 2) {
			mn = min(mn, n);
			for (int u : v) cand[u] = 1;
		}
	}
	
	return mn <= N / 2 || check(N) ? R : - R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:82:34: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   82 |  int s = max_element(hs, hs + N) - hs;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:87:34: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   87 |  int t = max_element(hs, hs + N) - hs;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:115:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  115 |   int p = vp.first, n = v.size();
      |                         ~~~~~~^~

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