Submission #1057202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057202		UmairAhmadMirza	Towns (IOI15_towns)	C++17	35 / 100	14 ms	1116 KiB

towns

#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,r1=0,r2=0;
	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++;
			else
				com_u++;
		}
		else{
			if(ubl==red)
				r2++;
			else
				com_v++;
		}
	}
	int hlf=N/2;
	if(com_v>hlf || com_u>hlf || r1>hlf || r2>hlf)
		red*=-1;
	return red;
}

Compilation message (stderr)

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

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