Submission #430128

#	Time	Username	Problem	Language	Result	Execution time	Memory
430128		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 p[1005];

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 or below > n/2) continue;
		
		vector<thing> check;
		for(thing x : stuff) if(x.adis == P.first) check.push_back(x);
		
		thing rep = {-1,-1,-1};
		vector<thing> nxt;
		
		for(int i = 0;i < n;i++) p[i] = i;
		while(true){
			if(check.empty()) break;
			for(int i = 0;i < sz(check);i += 2){
				if(i+1 == sz(check)) rep = check[i];
				else{
					thing a = check[i], b = check[i+1];
					if(query(a.i, b.i) != a.idis + b.idis){
						p[b.i] = a.i;
						nxt.push_back(a);
					}
				}
			}
			
			swap(nxt, check);
			nxt.clear();
		}
		
		if(rep.i == -1) continue;
		
		int big = 0;
		for(thing x : stuff){
			if(x.adis == P.first){
				int u = x.i;
				while(u != p[u]) u = p[u];
				
				if(query(u, rep.i) != rep.idis + x.idis) big++;
			}
		}
		
		if(big <= n/2) can = true;
	}
	
	if(can) return ans;
	return -ans;
}

Compilation message (stderr)

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