Submission #429578

#	Time	Username	Problem	Language	Result	Execution time	Memory
429578		oolimry	Towns (IOI15_towns)	C++17	100 / 100	38 ms	920 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 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;
		
		vector<thing> extra;
		while(true){
			if(sz(check) == 0) break;
			if(sz(check) == 1){
				rep = check[0];
				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){
						nxt.push_back(a);
						p[b.i] = a.i;
					}
				}
			}
			
			swap(check, nxt);
			nxt.clear();
		}
		
		if(rep.i == -1){
			can = true;
			continue;
		}
		
		int big = 0;
		
		map<int,int> solved;
		solved[rep.i] = 1;
		for(thing x : stuff){
			if(x.adis != P.first) continue;
			
			int u = x.i;
			while(p[u] != u) u = p[u];
			
			if(solved.find(u) == solved.end()){
				int res = (query(x.i, rep.i) != x.idis + rep.idis);
				big += res;
				solved[u] = res;
			}
			else big += solved[u];
			
			//show2(solved[u], x.i);
		}
		
		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:29:28: warning: unused parameter 'sub' [-Wunused-parameter]
   29 | int hubDistance(int N, int sub){
      |                        ~~~~^~~

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