Submission #1098345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098345		alexander707070	Towns (IOI15_towns)	C++14	0 / 100	29 ms	27780 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];

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

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

	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];

		vector< pair<int,int> > z={v[b][0]};
		vector<int> sz={1};
		int maxsz=1;

		for(int i=1;i<v[b].size();i++){
			bool ok=false;

			for(int f=0;f<z.size();f++){
				if(v[b][i].second+z[f].second > getDistance(v[b][i].first,z[f].first)){
					sz[f]++;
					maxsz=max(maxsz,sz[f]);
					ok=true; 
					break;
				}
			}

			if(!ok){
				z.push_back(v[b][i]);
				sz.push_back(1);
			}

			if(maxsz>n/2)break;
		}

		if(maxsz<=n/2){
			mult=1; break;
		}
	}

	return r*mult;
}

Compilation message (stderr)

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

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