Submission #1038005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038005		anton	Towns (IOI15_towns)	C++17	100 / 100	11 ms	1088 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>

const int MAX_N= 110;

struct Edge{
	int origin, dest;
	int l;
	Edge(){};
	Edge(int _or, int _de, int _l){
		l = _l;
		origin = _or;
		dest = _de;
	}
};


int distances[MAX_N][MAX_N];
bool queried[MAX_N][MAX_N];
int getDist(int a, int b){
	if(a == b){
		return 0;
	}
	if(!queried[a][b]){
		distances[a][b] = getDistance(a, b);
		distances[b][a] = distances[a][b];
		queried[a][b] = true;
		queried[b][a] = true;
	}
	return distances[a][b];

}
int n;


map<int, int> get_pos(int a, int b){
	map<int, int> cats;

	for(int i = 0; i<n; i++){
		cats[((getDist(a, i)-getDist(b, i))+getDist(a, b))/2]++;
	}

	return cats;
}

int find_pos(pair<int, int> axis, int i){
	int a = axis.first, b=  axis.second;
	return ((getDist(a, i)-getDist(b, i))+getDist(a, b))/2;
}

struct Base{
	pii axis;
	int rootPos;
	Base(pii a, int rp){
		axis = a;
		rootPos = rp;
	}
	
};

bool belongs(Base b, int i){
	return find_pos(b.axis, i)> b.rootPos;
}

struct DSU{
	int len;
	vector<int> sz, anc;
	vector<int> belongs;
	vector<vector<int>> rivals;


	DSU(int _len){
		len= _len;
		sz.resize(len, 1);
		anc.resize(len);
		belongs.resize(len, 0);
		rivals.resize(len);
		for(int i = 0; i<len; i++){
			anc[i]=i;
		}
	}


	void add_rival(int u, int r){
		rivals[C(u)].push_back(r);
	}
	int C(int u){
		if(anc[u] == u){
			return u;
		}
		int v = C(anc[u]);
		anc[u] = v;
		return v;
	}

	void merge(int a, int b){
		a = C(a);
		b = C(b);
		if(a == b){
			return;
		}
		if(sz[a]<sz[b]){
			swap(a, b);
		}

		anc[b] = a;
		sz[a] += sz[b];
		if(abs(belongs[b])>0){
			belongs[a] = belongs[b];
		}
		for(auto e: rivals[b]){
			rivals[a].push_back(e);
		}
	}
};

int find_sz_big(pair<int, int> axis, int root_pos){
	vector<Base> cur_group = {};

	DSU friends(n);

	friends.add_rival(axis.first, axis.second);
	friends.add_rival(axis.second, axis.first);

	int dist = getDist(axis.first, axis.second);

	for(int i = 0; i<n; i++){
		if(i!= axis.second && i!=axis.first){
			if(cur_group.size()== 0 || belongs(cur_group[0], i)){
				if(cur_group.size()>0){
					friends.merge(cur_group[0].axis.second, i);
				}
				if(getDist(axis.first, i)>=root_pos){
					cur_group.push_back(Base({axis.first, i}, root_pos));
				}
				else{
					cur_group.push_back(Base({axis.second, i}, dist-root_pos));
				}
				
			}
			else{
				friends.add_rival(i, cur_group.back().axis.second);
				friends.add_rival(cur_group.back().axis.second, i);
				cur_group.pop_back();
			}
		}
	}

	if(cur_group.size() == 0){
		return 0;
	}

	Base cand=  cur_group.back();

	int id = friends.C(cand.axis.second);
	friends.belongs[id] = 1;
	for(auto e: friends.rivals[id]){
		friends.belongs[friends.C(e)] = -1;
	}

	for(int i = 0; i<n; i++){
		int u = friends.C(i);
		if(abs(friends.belongs[u])<1){
			if(belongs(cand, u)){
				friends.belongs[u] = 1;
				for(auto e : friends.rivals[u]){
					friends.belongs[friends.C(e)] = -1;
				}
			}
			else{
				friends.belongs[u] = -1;
			}
		}
	}
	int maxSZ = 0;
	for(int i = 0; i<n; i++){
		if(friends.belongs[friends.C(i)] == 1){
			maxSZ ++;
		}
	}

	return maxSZ;
}
int R = 0;
int max_dist = 0;


pair<pair<int, int>, int> find_axis(){
	int rec = 0;
	int next = 1;
	int cur = 0;
	for(int i = 0; i<n; i++){
		if(getDist(cur, i)>rec){
			rec = getDist(cur, i);
			next=  i;
		}
	}
	rec=  0;
	cur= next;
	for(int i = 0; i<n; i++){
		if(getDist(cur, i)>rec){
			rec = getDist(cur, i);
			next=  i;
		}
	}
	return {{cur, 0}, getDist(cur, next)};
}
pair<int, int> axis;

void find_center(){
	
	auto r= find_axis();
	axis = r.first;
	int i = axis.first, j = axis.second;
	int dist_total = r.second;
	auto v = get_pos(i, j);
	int pathR = 1e9;
	for(auto mid: v){
		pathR = min(pathR, max(mid.first,dist_total-mid.first));

	}
	R = pathR;
	max_dist = dist_total;
	axis = {i, j};
	
}



int hubDistance(int N, int sub) {

	fill(&queried[0][0], &queried[MAX_N-1][MAX_N], false);

	n= N;
	
	

	find_center();
	if(sub == 2){
		return R;
	}
	int min_big_child = 1e9;


	if(sub == 4){
		auto v = get_pos(axis.first, axis.second);
		int left= 0;
		for(auto e: v){
			int mid = e.second;
			int right = n -left-mid;
			if(max(e.first, max_dist-e.first) == R){
				if(left<=n/2 && right <= n/2 && mid<=n/2){
					return R;
				}
			}
			left += e.second;

		}

		return -R;
	}

	int left= 0;

	for(auto e : get_pos(axis.first, axis.second)){
		int mid = e.second;
		int right = n -left-mid;
		if(max(e.first, max_dist-e.first) == R && (left<=n/2 && right<= n/2)){
			int v= find_sz_big(axis, e.first);
			min_big_child= min(min_big_child, v);
		
		}
		if(min_big_child <= (N/2)){
			return R;
		}
		left+= e.second;
	}
	if(min_big_child <= (N/2)){
		return R;
	}
	else{
		return -R;
	}
}

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