Submission #127458

#	Time	Username	Problem	Language	Result	Execution time	Memory
127458		kingfran1907	Towns (IOI15_towns)	C++14	0 / 100	2 ms	376 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 n;
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) {
	for (int i = 0; i < n * n; i++) getDistance(0, 1);
	::n = n;
	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)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:30:31: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 int hubDistance(int n, int sub) {
                               ^
towns.cpp:14:5: note: shadowed declaration is here
 int n;
     ^
towns.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < v.size(); i++) {
                  ~~^~~~~~~~~~
towns.cpp:89: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:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < li.size(); i++) 
                  ~~^~~~~~~~~~~
towns.cpp:30:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int n, int sub) {
                            ^~~

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