oj.uz

Submission #1057311

# Submission time Handle Problem Language Result Execution time Memory
1057311 2024-08-13T17:01:43 Z UmairAhmadMirza Towns (IOI15_towns) C++17
35 / 100
 9 ms 544 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]=-1;
			if(i==j)
				dis[i][j]=0;
		}
	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;
		red=min(red,max(bi-t,ci-t));
	}
	int u=b;
	int v=c;
	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 || min(r1+com_u,r2+com_v)>hlf)
			red*=-1;
		return red;
	}
	//check all
	if(com_v>hlf || com_u>hlf)
		red*=-1;
	if(r1>hlf){
		// 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;
		// }
	}
	if(r2>hlf){
		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;
		}
	}
	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 532 KB Output is correct
5 Correct 8 ms 468 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 348 KB Output is correct
2 Correct 6 ms 544 KB Output is correct
3 Correct 9 ms 344 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 Incorrect 7 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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