Submission #428080

#	Time	Username	Problem	Language	Result	Execution time	Memory
428080		oolimry	Towns (IOI15_towns)	C++17	Compilation error	0 ms	0 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<int,int> ii;

int DISTANCE[1000][1000];
int getDistance(int a, int b){
	return DISTANCE[a][b];
}

int n;
map<ii,int> M;
inline int query(int a, int b){
	if(M.find(ii(a,b)) != M.end()) return M[ii(a,b)];
	int res = getDistance(a,b);
	M[ii(a,b)] = res;
	M[ii(b,a)] = res;
	return res;
}

struct thing{
	int i, idis, adis; 
};

int hubDistance(int N, int sub) {
	M.clear();
	n = N;
	
	int A = 0;
	int B = 1;
	for(int i = 1;i < n;i++){
		if(query(A, B) < query(A, i)) B = i;
	}
	
	map<int, vector<int> > paths;
	map<int, vector<int> > good;
	vector<thing> stuff;
	
	for(int i = 0;i < n;i++){
		if(i == A or i == B) continue;
		
		int idis = (query(i,A)+query(i,B)-query(A,B)) / 2;
		int adis = query(i,A) - idis;
				
		paths[adis].push_back(i);
		stuff.push_back({i,idis,adis});
	}
	
	int ans = 102345678;
	for(auto P : paths){
		int adis = P.first, bdis = query(A,B) -  adis;
		int maxv = max(adis, bdis);
		for(thing x : stuff){
			maxv = max(maxv, x.idis + abs(x.adis-adis));
		}
		ans = min(ans, maxv);
	}
	
	for(auto P : paths){
		int adis = P.first, bdis = query(A,B) -  adis;
		int maxv = max(adis, bdis);
		for(thing x : stuff){
			maxv = max(maxv, x.idis + abs(x.adis-adis));
		}
		if(maxv == ans) good[P.first] = P.second;
	}
	
	bool can = false;
	for(auto P : good){
		int above = 1, below = 1;
		for(thing x : stuff){
			if(x.adis < P.first) above++;
			else if(x.adis > P.first) below++;
		}
		
		if(above <= n/2 and below <= n/2 and sz(P.second) <= n/2) can = true;
	}
	
	if(can) return ans;
	return -ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:32:28: warning: unused parameter 'sub' [-Wunused-parameter]
   32 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
/usr/bin/ld: /tmp/ccXluGp8.o: in function `getDistance(int, int)':
grader.c:(.text+0x110): multiple definition of `getDistance(int, int)'; /tmp/ccVKNKT8.o:towns.cpp:(.text+0x490): first defined here
collect2: error: ld returned 1 exit status