제출 #1037718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1037718		anton	도시들 (IOI15_towns)	C++17	26 / 100	117 ms	1032 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;


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

	for(int i = 0; i<n; i++){
		cats.insert(((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;
}

int find_sz_big(pair<int, int> axis, int root_pos){
	vector<pair<Base, vector<int>>> groups;
	groups.push_back({Base(axis, root_pos), {}});
	groups.push_back({Base({axis.second, axis.first}, getDist(axis.first, axis.second)-root_pos), {}});

	for(int i = 0; i<n; i++){
		bool found= false;
		for(pair<Base, vector<int>>& g: groups){
			if(belongs(g.first, i)){
				g.second.push_back(i);
				found = true;
				break;
			}
		}
		if(!found){
			groups.push_back({Base({axis.first, i}, root_pos), {i}});
		}
	}

	int maxSZ = 0;
	for(auto e: groups){
		maxSZ = max(maxSZ, (int)e.second.size());
	}
	return maxSZ;

}
int hubDistance(int N, int sub) {

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

	n= N;
	int R = 0;
	int max_dist = 0;
	pair<int, int> axis;
	for(int i = 0; i<N; i++){
		for(int j = i+1; j<N; j++){
			if(getDist(i, j)>R){
				int dist_total = getDist(i, j);
				auto v = get_pos(i, j);
				int pathR = 1e9;
				for(auto mid: v){
					pathR = min(pathR, max(mid,dist_total-mid));

				}
				if(pathR > R || dist_total > max_dist){
					R = pathR;
					max_dist = dist_total;
					axis = {i, j};
				}

			}
		}
	}


	int min_big_child = 1e9;

	for(auto e : get_pos(axis.first, axis.second)){
		int dist_total = getDist(axis.first, axis.second);
		if(max(e, dist_total-e) == R){
			min_big_child= min(min_big_child, find_sz_big(axis, e));
		}
	}
	if(min_big_child <= (N/2)){
		return R;
	}
	else{
		return -R;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:94:28: warning: unused parameter 'sub' [-Wunused-parameter]
   94 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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