oj.uz

Submission #1057228

# Submission time Handle Problem Language Result Execution time Memory
1057228 2024-08-13T15:38:00 Z UmairAhmadMirza Towns (IOI15_towns) C++17
35 / 100
 9 ms 860 KB 
#include <bits/stdc++.h>
using namespace std;

int const NN=120;
int dis[NN][NN];

int getDistance(int i, int j);
int hubDistance(int N, int sub){
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			dis[i][j]=-int(i!=j);
	int b=0;
	for(int i=1;i<N;i++){
		dis[0][i]=dis[i][0]=getDistance(0,i);
		if(dis[0][i]>=dis[0][b])
			b=i;
	}
	int c=0;
	for(int i=1;i<N;i++)
		if(i!=b){
			dis[i][b]=dis[b][i]=getDistance(i,b);
			if(dis[b][i]>=dis[b][c])
				c=i;
		}
	int bc=dis[b][c];
	for(int i=1;i<N;i++)
		if(i!=b && i!=c)
			dis[c][i]=dis[i][c]=getDistance(i,c);
	int red=bc;
	vector<pair<int,int>> black;
	for(int i=0;i<N;i++){
		int bi=dis[b][i];
		int ci=dis[c][i];
		int t=((bi+ci)-bc)/2;
		black.push_back({bi-t,ci-t});
		red=min(red,max(bi-t,ci-t));
	}
	int u=b;
	int v=c;
	sort(black.begin(), black.end());
	set<int> leaf;
	int com_u=0,com_v=0;
	int r1=0,r2=0;
	vector<int> rd1,rd2;
	for(int i=0;i<N;i++){
		int t=((dis[u][i]+dis[v][i]-bc)/2);
		int ubl=dis[u][i]-t;
		int vbl=dis[v][i]-t;
		if(ubl<=vbl){
			if(vbl==red){
				r1++;
				rd1.push_back(i);
			}
			else
				com_u++;
		}
		else{
			if(ubl==red){
				r2++;
				rd2.push_back(i);
			}
			else
				com_v++;
		}
	}
	int hlf=N/2;
	if(sub!=3){
		if(com_v>hlf || com_u>hlf || r1>hlf || r2>hlf)
			red*=-1;
		return red;
	}
	//check all
	for(int l1:rd1){
		int com=0;
		for(int l2:rd1){
			if(dis[l1][l2]==-1)
				dis[l1][l2]=dis[l2][l1]=getDistance(l1,l2);
			int d=dis[v][l1]+dis[v][l2]-dis[l1][l2];
			if(d>red*2)
				com++;
		}
		if(com>hlf)
			return -red;
	}
	for(int l1:rd2){
		int com=0;
		for(int l2:rd2){
			if(dis[l1][l2]==-1)
				dis[l1][l2]=dis[l2][l1]=getDistance(l1,l2);
			int d=dis[u][l1]+dis[u][l2]-dis[l1][l2];
			if(d>red*2)
				com++;
		}
		if(com>hlf)
			return -red;
	}
	if(com_u>hlf||com_v>hlf)
		return -red;
	return red;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 348 KB Output is correct
5 Correct 8 ms 536 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 536 KB Output is correct
2 Correct 6 ms 544 KB Output is correct
3 Correct 8 ms 536 KB Output is correct
4 Correct 8 ms 348 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 9 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 348 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -