Submission #127454

#	Time	Username	Problem	Language	Result	Execution time	Memory
127454		kingfran1907	Towns (IOI15_towns)	C++14	Compilation error	0 ms	0 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) {
	assert(a < n && b < n && a >= 0 && b >= 0);
	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);
	a = b = B = 0;
	//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;
	int hu = -1, out = inf;
	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 (out > max(ad, bd)) out = max(ad, bd), hu = ad;
	}

	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);
	}

	if (max(lef, rig) > n / 2) return -out;

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

	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 -out;
	else return out;
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from towns.cpp:2:
towns.cpp: In function 'int query(int, int)':
towns.cpp:15:13: error: 'n' was not declared in this scope
  assert(a < n && b < n && a >= 0 && b >= 0);
             ^
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:29:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int n, int sub) {
                            ^~~