Submission #127449

#	Time	Username	Problem	Language	Result	Execution time	Memory
127449		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 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];
}

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) {
  	int qs[maxn][maxn];
	int sol[maxm];
	vector<int> v;
	vector<int> li, buk;
  	int a, b;
	int B;
  
	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;
	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)

towns.cpp: In function 'int query(int, int)':
towns.cpp:11:6: error: 'qs' was not declared in this scope
  if (qs[a][b] == -1) qs[a][b] = getDistance(a, b);
      ^~
towns.cpp:12:9: error: 'qs' was not declared in this scope
  return qs[a][b];
         ^~
towns.cpp: In function 'bool subtree(int, int)':
towns.cpp:16:18: error: 'a' was not declared in this scope
  int xd = (query(a, x) + query(b, x) - query(a, b)) / 2;
                  ^
towns.cpp:16:32: error: 'b' was not declared in this scope
  int xd = (query(a, x) + query(b, x) - query(a, b)) / 2;
                                ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < v.size(); i++) {
                  ~~^~~~~~~~~~
towns.cpp:84: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:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < li.size(); i++) 
                  ~~^~~~~~~~~~~
towns.cpp:23:6: warning: unused variable 'sol' [-Wunused-variable]
  int sol[maxm];
      ^~~
towns.cpp:21:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int n, int sub) {
                            ^~~