Submission #105461

#	Time	Username	Problem	Language	Result	Execution time	Memory
105461		CaroLinda	Towns (IOI15_towns)	C++14	25 / 100	25 ms	768 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
 
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define ff first
#define ss second
#define pb push_back
#define pii pair<int,int>
#define MAXN 120
 
const int inf = 1e9 + 5 ; 
 
using namespace std;
 
//
int N  , A , B  , R ;
int perp[MAXN] ;
int d[MAXN][MAXN] ;
bool marc[MAXN][MAXN] ;
//
 
void init()
{
  memset( d , 0 , sizeof d ) ;
  memset(marc , 0 , sizeof marc ) ;
  lp(i,0,MAXN) marc[i][i] = 1 ;
  R = inf ;
}
 
void ask( int x , int y )
{
  if( marc[x][y] ) return ;
  d[x][y] = d[y][x] = getDistance(x,y) ;
  marc[x][y] = marc[y][x] = 1 ;
}
 
bool check( vector<int> &s )
{
  if( s.size() == 0 ) return 1 ;
 
  int buck = 0 , ff = s[0] ;
 
  for( auto i : s )
  {
    int v = s[i] ;
    ask(v,ff) ;
    if(d[v][ff] == perp[i] + perp[v])
    {
      if(buck == 0) buck = 1 , ff = v ;
      else buck -- ;
    }
    else buck ++ ;
  }
 
  buck = s.size() ;
  for(auto i : s)
  {
    ask( ff , i ) ;
    if( d[ff][i] == perp[i] + perp[ff] ) buck -- ;
  }
 
  return (buck <= N/2) ;
}

int sub4()
{
  int l = 0 , r = 0 , mid = 0 , man = -1;
  lp(i,0,N){
    if( d[A][i] == R ) man = A ;
    else if (d[B][i] == R) man =B ;
    if(man!=-1) break ;
  }

  lp(i,0,N)
  {
    if(d[man][i] - perp[i] < R) l++ ;
    else if( d[man][i] - perp[i] > R ) r++ ;
    else mid ++ ;
  }

  if( l > N/2 or r > N/2 or mid > N/2 ) return -1 ;
  return 1 ;

}
 
int hubDistance( int n , int sub)
{
	N = n ;
  vector<int> s ;
  int balanced = 0 ;
	init() ;
 
  lp(i,0,n) ask(0,i) ;
  A = max_element( d[0] , d[0]+n )- d[0] ;
  lp(i,0,N) ask(A , i) ;
  B = max_element( d[A] , d[A] + n ) - d[A] ;
  lp(i,0,N) ask(B , i) ;
 
  lp(i,0,n) perp[i] = ( d[A][i] + d[B][i] - d[A][B] ) / 2 ;
  lp(i,0,n)
    R = min( R , max( d[A][i] , d[B][i] ) - perp[i] ) ;
  
  if( sub < 3 ) return R ;
  if( sub == 4 ) return R * sub4() ;
 
  int l = 0 , r = 0 ;

  lp(i,0,n){
    if( d[A][i] - perp[i] == R )
      s.pb(i) ;
    else if( d[A][i] - perp[i] < R ) l ++ ;
    else r ++ ;
  }
  
  if( r <= N/2 and l <= N/2  )
  balanced |= check(s) ;
 
  s.resize(0) ;
  l = 0 , r = 0 ;
  lp(i,0,n){
    if( d[B][i] - perp[i] == R )
      s.pb(i) ;
    else if( d[B][i] - perp[i] < R ) l ++ ;
    else r++ ;
  }
  
  if(l <= N/2 and r <= N/2)
  balanced |= check(s) ;
 
  return R * (balanced ? 1 : -1) ;
 
}

Compilation message (stderr)

towns.cpp: In function 'bool check(std::vector<int>&)':
towns.cpp:55:16: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   buck = s.size() ;
          ~~~~~~^~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:94:35: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   A = max_element( d[0] , d[0]+n )- d[0] ;
       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:96:38: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   B = max_element( d[A] , d[A] + n ) - d[A] ;
       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~

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