제출 #105438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105438		CaroLinda	도시들 (IOI15_towns)	C++14	35 / 100	32 ms	512 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 , man;
int perp[MAXN] ;
int v[] = {0,0,0} ;
int d[MAXN][MAXN] ;
bool marc[MAXN][MAXN] ;
//
 
//union-find stuff
int pai[MAXN]  , h[MAXN];

void init()
{
	memset( v , 0 , sizeof v  ) ;
	lp(i,0,N) pai[i] = i ;
	memset( h , 0 , sizeof h ) ;
  memset(marc , 0 , sizeof marc ) ;
  lp(i,0,N) marc[i][i] = 1 ;
}
 
int getDist( int x , int y )
{
  if( marc[x][y] ) return d[x][y] ;
  marc[x][y] = marc[y][x] = 1 ;
  d[x][y] = d[y][x] = getDistance( x , y ) ;
  return d[x][y] ;
}
 
void query( int x )
{ lp(i,0,N) d[x][i] = getDist( x, i ) ; }
 
int findMax( int x )
{ return max_element(d[x] , d[x] + N) - d[x] ; }
 
int findPerpendicular( int x )
{ return (d[A][x] + d[B][x] - d[A][B])/2 ; }
 
int findRadio()
{
	int ans = inf ;
	lp(i,0,N)
	{
		int k = max( d[A][i] , d[B][i] ) - perp[i] ;
		int Man = d[A][i] > d[B][i] ? A : B ;
		if( k < ans ) ans = k , man = Man ;
	}
	return ans ;
}
 
int checkPosition( int x )
{
	int k = d[man][x] - perp[x] ;
	if( k < R ) return 0 ;
	if( k == R ) return 1 ;
	return 2 ;
}

int sub4()
{
	lp(i,0,N)
		v[ checkPosition(i) ] ++ ;
	lp(i,0,3)
		if( v[i] > N/2 ) return -R ;
	return R ;
}
 
bool check( vector<int> &vec )
{
  if(vec.size() <= N/2) return 1 ;
  int bucket = 0 , now = vec[0] ;
  lp( i , 1 , vec.size() )
  {
    if( getDist( now , vec[i]) == perp[now] + perp[ vec[i] ] )
    {
      //different componentes
      if( !bucket ) now = vec[i] , bucket = 1;
      else bucket -- ;
    }
    bucket ++ ;
  }

  bucket = vec.size() ;

  for(auto it : vec)
    if( getDist(now , it) == perp[now] + perp[it] ) bucket -- ;

  return (bucket <= N/2) ;

}

int hubDistance( int n , int sub)
{
	N = n ;
	init() ;
	query(0) ;
	A = findMax(0) ;
	query(A) ;
	B = findMax(A) ;
	query(B) ;
	lp(i,0,n) perp[i] = findPerpendicular(i) ;
	R = findRadio() ;
	if( sub < 3 ) return R ;
	if( sub == 4 ) return sub4() ;

  vector<int> s  ;
  bool balanced = 0 ;
  lp(i,0,N)
  {
    s.resize(0) ;
    if( d[A][i] - perp[i] == R )
    {
      man = A ;
      lp(j,0,N)
        if( checkPosition(j) == 1) s.pb(j) ;
      balanced |= check(s) ; 
    }
    if( d[B][i] - perp[i] == R )
    {
      man = B ;
      lp(j,0,N)
        if( checkPosition(j) == 1) s.pb(j) ;
      balanced |= check(s) ;
    }
  }

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

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'int findMax(int)':
towns.cpp:47:39: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
 { return max_element(d[x] , d[x] + N) - d[x] ; }
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp: In function 'bool check(std::vector<int>&)':
towns.cpp:83:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(vec.size() <= N/2) return 1 ;
      ~~~~~~~~~~~^~~~~~
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:85:7:
   lp( i , 1 , vec.size() )
       ~~~~~~~~~~~~~~~~~~             
towns.cpp:85:3: note: in expansion of macro 'lp'
   lp( i , 1 , vec.size() )
   ^~
towns.cpp:96:20: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   bucket = vec.size() ;
            ~~~~~~~~^~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:140:28: warning: ?: using integer constants in boolean context, the expression will always evaluate to 'true' [-Wint-in-bool-context]
 balanced = (balanced == 1) ? 1 : -1 ;
            ~~~~~~~~~~~~~~~~^~~~~~~~

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