oj.uz

답안 #1037755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1037755 2024-07-29T07:47:45 Z anton 도시들 (IOI15_towns) C++17
38 / 100
 21 ms 544 KB 
#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<Base> cur_group = {Base(axis, root_pos)};
	
	for(int i = 0; i<n; i++){
		if(i!= axis.second ){
			if(cur_group.size()== 0 || belongs(cur_group[0], i)){
				cur_group.push_back(Base({axis.first, i}, root_pos));
			}
			else{
				cur_group.pop_back();
			}
		}
	}

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

	Base cand=  cur_group.back();

	int maxSZ = 0;
	for(int i = 0; i<n; i++){
		if(belongs(cand, i)){
			maxSZ ++;
		}
	}
	return maxSZ;
}
int R = 0;
int max_dist = 0;


pair<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, next};
}
pair<int, int> axis;

void find_center(){
	
	axis= find_axis();
	int i = axis.first, j = axis.second;
	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));

	}
	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;

	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;
	}
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 344 KB Output is correct
2 Correct 7 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 9 ms 544 KB Output is correct
5 Correct 21 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 344 KB Output is correct
2 Correct 9 ms 348 KB Output is correct
3 Correct 10 ms 348 KB Output is correct
4 Correct 21 ms 344 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 10 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 10 ms 344 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -