Submission #127422

#	Time	Username	Problem	Language	Result	Execution time	Memory
127422		kingfran1907	Towns (IOI15_towns)	C++14	35 / 100	69 ms	4988 KiB

towns

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

using namespace std;
const int maxn = 120;
const int maxm = 1e6+10;
const int inf = 0x3f3f3f3f;

int qs[maxn][maxn];
int sol[maxm];
vector<int> v;
vector<int> li, buk;

int query(int a, int b) {
	if (a > b) swap(a, b);
	if (qs[a][b] == -1) qs[a][b] = getDistance(a, b);
	return qs[a][b];
}

int a, b;
int B;
bool subtree(int x, int y) {
	int xd = (query(a, x) + query(b, x) - query(a, b)) / 2;
	int yd = (query(a, y) + query(b, y) - query(a, b)) / 2;
	return (xd + yd - query(x, y)) > 0;
}

int hubDistance(int n, int sub) {
	memset(qs, -1, sizeof qs);
	memset(sol, inf, sizeof sol);

	for (int i = 0; i < n; i++)
		qs[i][i] = 0;

	a = 0, b = 0;
	for (int i = 0; i < n; i++)
		if (query(0, a) < query(0, i)) a = i;

	for (int i = 0; i < n; i++)
		if (query(a, b) < query(a, i)) b = i;
	
	B = b; b = 0;
	for (int i = 0; i < n; i++) {
		int cd = (query(a, i) + query(b, i) - query(a, b)) / 2;
		int ad = query(a, i) - cd;
		int bd = query(a, B) - ad;

		if (sol[ad] == inf) sol[ad] = 0;
		sol[ad] = max({sol[ad], cd, ad, bd});
	}

	int hu = 0;
	for (int i = 0; i < maxm; i++) 
		if (sol[hu] > sol[i]) hu = i;

	int lef = 0, rig = 0;
	v.clear();
	for (int i = 0; i < n; i++) {
		int cd = (query(a, i) + query(b, i) - query(a, b)) / 2;
		int ad = query(a, i) - cd;

		if (ad < hu) lef++;
		else if (ad > hu) rig++;
		else v.push_back(i);
	}

	li.clear();
	buk.clear();
	if (v.size() == 0) {
		if (max(lef, rig) > n / 2) return -sol[hu];
		else return sol[hu];
	}

	li.push_back(v[0]);
	for (int i = 1; i < v.size(); i++) {
		if (subtree(v[i], li.back())) buk.push_back(v[i]);
		else {
			li.push_back(v[i]);
			if (!buk.empty()) {
				li.push_back(buk.back());
				buk.pop_back();
			}
		}
	}

	int cnt = buk.size();
	for (int i = 0; i < li.size(); i++) 
		if (subtree(li[i], li.back())) cnt++, i++;

	if (max({cnt, lef, rig}) > n / 2) return -sol[hu];
	else return sol[hu];
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < v.size(); i++) {
                  ~~^~~~~~~~~~
towns.cpp:86:20: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int cnt = buk.size();
            ~~~~~~~~^~
towns.cpp:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < li.size(); i++) 
                  ~~^~~~~~~~~~~
towns.cpp:28:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int n, int sub) {
                            ^~~

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