Submission #1098356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098356		alexander707070	Towns (IOI15_towns)	C++14	26 / 100	55 ms	29276 KiB

towns

#include<bits/stdc++.h>
#include "towns.h"

#define MAXN 200

using namespace std;

int n,r,mult;
int dist[MAXN],s,t,diameter,dist2[MAXN],pref[1000007];

vector< pair<int,int> > v[1000007];
bool checked[1000007];

int hubDistance(int N, int sub) {
	int n=N; mult=-1;

	for(int i=0;i<=1000000;i++){
		v[i].clear(); pref[i]=0; checked[i]=false;
	}

	s=0; dist[0]=0;
	for(int i=1;i<n;i++){
		dist[i]=getDistance(0,i);
		if(dist[i]>dist[s])s=i;
	}

	dist[s]=0; t=s;
	for(int i=0;i<n;i++){
		if(i==s)continue;
		dist[i]=getDistance(s,i);

		if(dist[i]>dist[t])t=i;
	}

	diameter=dist[t]; r=1000000;
	
	for(int i=0;i<n;i++){
		if(i==s or i==t)continue;

		dist2[i]=getDistance(t,i);
		int sum=(diameter+dist[i]+dist2[i])/2;

		v[sum-dist2[i]].push_back({i,sum-diameter});
		pref[sum-dist2[i]]++;

		r=min(r,max(sum-dist[i],sum-dist2[i]));
	}

	for(int i=1;i<=1000000;i++)pref[i]+=pref[i-1];

	for(int i=0;i<n;i++){
		if(i==s or i==t)continue;

		int sum=(diameter+dist[i]+dist2[i])/2;
		if(max(sum-dist[i],sum-dist2[i]) != r)continue;

		int a=pref[sum-dist2[i]-1]+1;
		int c=n-a-v[sum-dist2[i]].size();

		if(a>n/2 or c>n/2)continue;

		random_shuffle(v[sum-dist2[i]].begin(),v[sum-dist2[i]].end());
		
		int b=sum-dist2[i];

		if(checked[b])continue;
		checked[b]=true;

		if(v[b].size()<=n/2){
			mult=1; break;
		}

		int maxsz=1;
		bool ok=true;

		for(int i=0;i<min(int(v[b].size()),n/2-3);i++){
			maxsz=1;

			for(int f=0;f<v[b].size();f++){
				if(i==f)continue;

				if(v[b][i].second+v[b][f].second > getDistance(v[b][f].first,v[b][i].first))maxsz++;
			}

			if(maxsz>n/2){
				ok=false; break;
			}
		}

		if(ok){
			mult=1; break;
		}
	}

	return r*mult;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:15:6: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   15 |  int n=N; mult=-1;
      |      ^
towns.cpp:8:5: note: shadowed declaration is here
    8 | int n,r,mult;
      |     ^
towns.cpp:58:12: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   58 |   int c=n-a-v[sum-dist2[i]].size();
      |         ~~~^~~~~~~~~~~~~~~~~~~~~~~
towns.cpp:69:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |   if(v[b].size()<=n/2){
      |      ~~~~~~~~~~~^~~~~
towns.cpp:76:11: warning: declaration of 'i' shadows a previous local [-Wshadow]
   76 |   for(int i=0;i<min(int(v[b].size()),n/2-3);i++){
      |           ^
towns.cpp:51:10: note: shadowed declaration is here
   51 |  for(int i=0;i<n;i++){
      |          ^
towns.cpp:79:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |    for(int f=0;f<v[b].size();f++){
      |                ~^~~~~~~~~~~~
towns.cpp:14:28: warning: unused parameter 'sub' [-Wunused-parameter]
   14 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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