Submission #432954

#	Time	Username	Problem	Language	Result	Execution time	Memory
432954		Antekb	Towns (IOI15_towns)	C++14	100 / 100	24 ms	360 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
int hubDistance(int N, int sub) {
	//int R = getDistance(0,1);
	int d1[N], d2[N];
	d1[0]=0;
	for(int i=1; i<N; i++)d1[i]=getDistance(0, i);
	int e=0;
	for(int i=0; i<N; i++)if(d1[i]>d1[e])e=i;
	for(int i=1; i<N; i++)if(e!=i)d2[i]=getDistance(e, i);
	d2[e]=0;
	d2[0]=d1[e];
	int diam=0;
	for(int i=0; i<N; i++)diam=max(diam, d2[i]);
	int R=diam;
	for(int i=0; i<N; i++){
		if(i==0 || i==e)continue;
		int d=(d2[i]+d2[0]-d1[i])/2;
		R=min(R, max(d, diam-d));
	}
	int a=0, b=0;
	vector<int> A, B;
	for(int i=0; i<N; i++){
		int d=(d2[i]+d2[0]-d1[i])/2;
		if(d>diam-d){
			if(R<d)a++;
			else A.push_back(i);
		}
		else{
			if(diam-d==R)B.push_back(i);
			else b++;
		}
	}
	/*cerr<<a<<" "<<A.size()<<" "<<B.size()<<" "<<b<<"\n";
	for(int i:A)cerr<<i<<" ";
	cerr<<"\n";*/
	//if(A.size()>N/2 || B.size()>N/2 || a>N/2 || b>N/2)return -R;
	//return R;
	if(a>N/2)return -R;
	if(b>N/2)return -R;
	if(a+A.size()<=N/2 && B.size()<=N/2)return R;
	if(b+B.size()<=N/2 && A.size()<=N/2)return R;
	if(A.size()<B.size())swap(A, B);
	int dist[N];
	for(int i=0; i<N; i++){
		dist[i]=(d2[i]-d2[0]+d1[i])/2;
	}
	stack<int> S, S2;
	for(int i:A){
		if(S2.size()!=0 && dist[i]+dist[S2.top()]!=getDistance(i, S2.top())){
			S.push(i);
		}
		else{
			S2.push(i);
			if(S.size()){
				S2.push(S.top());
				S.pop();
			}
		}
	}
	S.push(S2.top());
	S2.pop();
	int cnt=S.size();
	while(S.size() && S2.size()){
		if(dist[S.top()]+dist[S2.top()]!=getDistance(S.top(), S2.top())){
			cnt++;
			S2.pop();
			if(S2.size())S2.pop();
		}
		else{
			S.pop();
			S2.pop();
		}
	}
	if(cnt>N/2)return -R;
	else return R;
	/*for(int i:A){
		if(!S.size() || dist[i]+dist[S.top()]!=getDistance(i, S.top()))S.push(i);
		else S.pop();
	}
	if(!S.size())return R;
	int cnt=0;
	for(int i:A){
		if(dist[i]+dist[S.top()]!=getDistance(i, S.top()))cnt++;
	}
	if(cnt>N/2)return -R;
	return R;*/
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:44:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |  if(a+A.size()<=N/2 && B.size()<=N/2)return R;
      |     ~~~~~~~~~~^~~~~
towns.cpp:44:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |  if(a+A.size()<=N/2 && B.size()<=N/2)return R;
      |                        ~~~~~~~~^~~~~
towns.cpp:45:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |  if(b+B.size()<=N/2 && A.size()<=N/2)return R;
      |     ~~~~~~~~~~^~~~~
towns.cpp:45:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |  if(b+B.size()<=N/2 && A.size()<=N/2)return R;
      |                        ~~~~~~~~^~~~~
towns.cpp:66:16: warning: conversion from 'std::stack<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   66 |  int cnt=S.size();
      |          ~~~~~~^~
towns.cpp:6:28: warning: unused parameter 'sub' [-Wunused-parameter]
    6 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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