Submission #1098329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098329		alexander707070	Towns (IOI15_towns)	C++14	25 / 100	99 ms	28496 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];
		int b=v[sum-dist2[i]].size();
		int c=n-a-b;
		
		if(a<=n/2 and b<=n/2 and c<=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:56:29: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   56 |   int b=v[sum-dist2[i]].size();
      |         ~~~~~~~~~~~~~~~~~~~~^~
towns.cpp:13:28: warning: unused parameter 'sub' [-Wunused-parameter]
   13 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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