Submission #105455

#	Time	Username	Problem	Language	Result	Execution time	Memory
105455		CaroLinda	Towns (IOI15_towns)	C++14	25 / 100	27 ms	640 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 = 1 , ff = s[0] ;

  lp(i,1,s.size())
  {
    int v = s[i] ;
    ask(v,ff) ;
    if(d[v][ff] == perp[i] + perp[v])
    {
      buck -- ;
      if(buck == 0) buck = 1 , ff = v ;
    }
    else buck ++ ;
  }

  buck = s.size() ;
  lp(i,0,N)
  {
    ask( ff , i ) ;
    if( d[ff][i] == perp[i] + perp[ff] ) buck -- ;
  }

  return (buck <= N/2) ;
}

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 ;

  lp(i,0,n)
    if( d[A][i] - perp[i] == R )
      s.pb(i) ;

  balanced |= check(s) ;

  s.resize(0) ;
  lp(i,0,n)
    if( d[B][i] - perp[i] == R )
      s.pb(i) ;
  
  balanced |= check(s) ;

  return R * (balanced ? 1 : -1) ;

}

Compilation message (stderr)

towns.cpp: In function 'bool check(std::vector<int>&)':
towns.cpp:4:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i = a ; i < b ; i++)
towns.cpp:43:6:
   lp(i,1,s.size())
      ~~~~~~~~~~~~                    
towns.cpp:43:3: note: in expansion of macro 'lp'
   lp(i,1,s.size())
   ^~
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:73: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:75: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