oj.uz

Submission #599385

# Submission time Handle Problem Language Result Execution time Memory
599385 2022-07-19T13:25:34 Z sofapuden Towns (IOI15_towns) C++14
100 / 100
 15 ms 892 KB 
#include "towns.h"
#include<bits/stdc++.h>

using namespace std;

vector<vector<int>> Q;

void que(int a, int b){
	if(Q[a][b] != -1)return;
	Q[a][b] = Q[b][a] = getDistance(a,b);
}

int hubDistance(int n, int sub) {
	Q.clear();
	Q.resize(n,vector<int>(n,-1));
	for(int i = 0; i < n; ++i)Q[i][i] = 0;
	int mx = -1;
	int ind = sub;
	for(int i = 0; i < n; ++i){
		que(0,i);
		if(Q[0][i] > mx){
			mx = Q[0][i];
			ind = i;
		}
	}
	int mx2 = -1;
	int ind2 = sub;
	for(int i = 0; i < n; ++i){
		que(ind,i);
		if(Q[ind][i] > mx2){
			mx2 = Q[ind][i];
			ind2 = i;
		}
	}
	int ans = 1<<30;
	vector<int> rad(n);
	for(int i = 0; i < n; ++i){
		rad[i] = (Q[0][ind]+Q[i][ind]-Q[0][i])>>1;
		ans = min(ans,max(rad[i],Q[ind][ind2]-rad[i]));
	}
	int cen = -1;
	for(int i = 0; i < n; ++i){
		if(ans == max(rad[i],Q[ind][ind2]-rad[i])){
			pair<int,int> cnt = {0,0};
			for(int j = 0; j < n; ++j){
				if(i == j || rad[i] == rad[j])continue;
				if(rad[i] > rad[j])cnt.first++;
				else cnt.second++;
			}
			if(max(cnt.first,cnt.second) <= n/2)cen = i;
		}
	}
	if(cen == -1)return -ans;

	int cn = 0;
	int mbe = 0;
	vector<int> go(n,0);
	map<int,bool> ba;
	for(int i = 0; i < n; ++i){
		if(rad[i] == rad[cen]){
			if(!cn) mbe = i, ba.clear();
			que(mbe,i);
			if(Q[mbe][i] < Q[ind][mbe]+Q[ind][i]-2*rad[mbe])cn++, go[mbe]++;
			else cn--, go[i] = 1, ba[i] = 1;
		}
	}
	int cnt = 0;
	for(int i = 0; i < n; ++i){
		if(rad[i] == rad[cen] && !ba[i] && go[i]){
			que(mbe,i);
			cnt+=(Q[mbe][i] < Q[ind][mbe]+Q[ind][i]-2*rad[mbe])*go[i];
		}
	}
	return cnt > n/2 ? -ans : ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Output is correct
2 Correct 10 ms 400 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 14 ms 392 KB Output is correct
5 Correct 15 ms 388 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 400 KB Output is correct
2 Correct 10 ms 340 KB Output is correct
3 Correct 14 ms 388 KB Output is correct
4 Correct 14 ms 876 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 400 KB Output is correct
2 Correct 14 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 14 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 340 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 15 ms 340 KB Output is correct
3 Correct 13 ms 392 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 14 ms 340 KB Output is correct
3 Correct 14 ms 892 KB Output is correct