oj.uz

Submission #71622

# Submission time Handle Problem Language Result Execution time Memory
71622 2018-08-25T08:50:57 Z Sa1378 Towns (IOI15_towns) C++17
26 / 100
 36 ms 5304 KB 
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define N ((int)230)

int dis[N],dis2[N],dis3[N];
map <int,vector <int> > mp[2];
bool mark[N];

int hubDistance(int n, int sub)
{
	mp[0].clear();mp[1].clear();
	int id=0,maxi=0;
	for(int i=1;i<n;i++)
	{
		int ex=getDistance(0,i);
		if(ex>maxi)maxi=ex,id=i;
	}
	dis[0]=maxi;dis[id]=0;
	int id2=0;
	for(int i=1;i<n;i++)
		if(i!=id)
		{
			dis[i]=getDistance(id,i);
			if(dis[i]>maxi)maxi=dis[i],id2=i;
		}
	dis2[id]=maxi;dis2[id2]=0;
	for(int i=0;i<n;i++)
		if(i!=id && i!=id2)
			dis2[i]=getDistance(id2,i);
	int R=(int)1e9;
	int cnt0=0;
	for(int i=0;i<n;i++)
	{
		bool p=(dis[i]>dis2[i]);
		if(p==0)cnt0++;
		int ex=(dis2[id]+abs(dis2[i]-dis[i]))/2;
		R=min(R,ex);
		mp[p][ex].push_back(i);
	}
	vector <int> vec;
	int x0=mp[0].begin()->first,x1=mp[1].begin()->first;
	if(x0==R && x1==R)
	{
		if(cnt0<=n/2)
		{
			vec=mp[1].begin()->second;
			if(n-cnt0-(int)vec.size()>n/2)return -R;
		}
		else
		{
			vec=mp[0].begin()->second;
			if(cnt0-(int)vec.size()>n/2)return -R;
		}
	}
	else if(x0==R)
	{
		vec=mp[0].begin()->second;
		if(n-cnt0>n/2 || cnt0-(int)vec.size()>n/2)return -R;
	}
	else
	{
		vec=mp[1].begin()->second;
		if(cnt0>n/2 || n-cnt0-(int)vec.size()>n/2)return -R;
	}
	if(vec.size()<=n/2)return R;
	memset(mark,0,sizeof mark);
	for(auto u:vec)
		dis3[u]=(dis[u]+dis2[u]-dis2[id])/2;
	for(auto u:vec)
	{
		if(mark[u])continue;
		int cnt=1;mark[u]=1;
		for(auto v:vec)
			if(!mark[v] && getDistance(u,v)!=dis3[u]+dis3[v])
				mark[v]=1,cnt++;
		if(cnt>n/2)return -R;
	}
	return R;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:66:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(vec.size()<=n/2)return R;
     ~~~~~~~~~~^~~~~
towns.cpp:10:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int n, int sub)
                            ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 888 KB Output is correct
2 Correct 19 ms 1468 KB Output is correct
3 Correct 3 ms 1536 KB Output is correct
4 Correct 36 ms 2160 KB Output is correct
5 Correct 24 ms 2840 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3316 KB Output is correct
2 Correct 29 ms 3900 KB Output is correct
3 Correct 3 ms 3984 KB Output is correct
4 Correct 24 ms 4500 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 5192 KB Output isn't correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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