oj.uz

Submission #169754

# Submission time Handle Problem Language Result Execution time Memory
169754 2019-12-22T15:36:11 Z CaroLinda Towns (IOI15_towns) C++14
100 / 100
 22 ms 1148 KB 
#include <bits/stdc++.h>
#include "towns.h"
 
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define ll long long
#define sz size()
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define tiii tuple<int,int,int>
#define mkt make_tuple
 
const int MAXN = 120 , inf = 1e9+10 ;
 
using namespace std ;
 
int n , v , s , t , r ;
int myRadio[MAXN] ;
int d[MAXN][MAXN] ;
stack<int> List, bucket ;
 
inline void ask(int i , int j)
{
 
	if( d[i][j] == -1 ) 
		d[i][j] = d[j][i] = getDistance(i,j) ;
 
}
 
bool isDiff(int i, int j)
{
	if( myRadio[i] < r && myRadio[j] < r ) return false ;
	else if( myRadio[i] > r && myRadio[j] > r ) return false ;
	if( !(myRadio[i] == myRadio[j] && myRadio[i] == r) ) return true ;
 
	ask(i,j) ;
	return d[s][i] + d[s][j] - d[i][j] == 2*r; 
}
 
void print(stack<int> a , stack<int> b )
{
 
	debug("Printing stacks\n") ;
	while(!a.empty()) debug("%d " , a.top() ) , a.pop() ;
	debug("\n") ;
	while(!b.empty()) debug("%d " , b.top() ) , b.pop() ;
	debug("\n\n") ;
 
}
 
int hubDistance(int N, int sub)
{
 
	memset(d, -1, sizeof d ) ;
	lp(i,0,N) d[i][i] =0  ;
 
	n = N ;
 
	lp(i,0,n) ask(0,i) ;
	v = 0 ;
 
	s = max_element( d[v] , d[v]+n ) - d[v] ;
 
	lp(i,0,n) ask(s,i) ;
	t = max_element( d[s] , d[s] + n ) - d[s] ;
 
 	r = inf ;
	
 	lp(i,0,n)
 	{
 
 		myRadio[i] = ( d[v][s] + d[s][i] - d[v][i] ) >> 1 ; 
 		r = min(r, max( myRadio[i] , d[s][t] - myRadio[i] )  ) ;
 
 	}

 	int R = r ;

 	if(sub <= 2) return R ;
 
 	int toLeftS=0 , toRightS=0 , toLeftT=0 , toRightT=0 ;
 	vector<int> auxS , auxT , toTest ;
 
 	lp(i,0,n)
 	{
 
 		if( myRadio[i] < r ) toLeftS ++ ;
 		else if( myRadio[i] > r ) toRightS ++ ;
 
 		int aux = d[s][t] - myRadio[i] ;
 
 		if( aux < r ) toRightT ++ ;
 		else if( aux > r ) toLeftT ++ ;
 
 	}
 
 	toLeftS = max(toLeftS, toRightS ) ;
 	toLeftT = max(toLeftT, toRightT ) ;
 
 	if( toLeftS > n/2 )
 	{
 		if( toLeftT > n/2 ) return -R ;
 		r = d[s][t] - r ;
 	}
 	
 	while( !List.empty() ) List.pop() ;
 	while( !bucket.empty() ) bucket.pop() ;

 
 	lp(i,0, n)
 	{
 
 		if( List.empty() || isDiff(List.top() ,i) )
 		{
 
 			List.push(i) ;
 			if( bucket.empty() ) continue ;
 			List.push( bucket.top() ) ;
 			bucket.pop() ;
 
 		}
 
 		else bucket.push(i) ;
 
 	}
 
 	int T = List.top() ;
 
 	while( !List.empty() )
 	{
 
 		if( isDiff(List.top() ,T) )
 		{
 
 			List.pop() ;
 
 			if( bucket.empty() ) return R ;
 
 			bucket.pop() ;
 
 
 		}
 
 		else
 		{
 
 			List.pop() ;
 			
 			if( List.sz == 0 ) bucket.push(T) ;
 
 			List.pop() ;
 
 		}
 
 	}
 
 	return ( bucket.empty() ?  R : -R ) ;
 
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:66:35: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  s = max_element( d[v] , d[v]+n ) - d[v] ;
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
towns.cpp:69:37: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  t = max_element( d[s] , d[s] + n ) - d[s] ;
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 504 KB Output is correct
2 Correct 16 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 21 ms 464 KB Output is correct
5 Correct 22 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 500 KB Output is correct
2 Correct 16 ms 376 KB Output is correct
3 Correct 21 ms 376 KB Output is correct
4 Correct 21 ms 376 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 504 KB Output is correct
2 Correct 21 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 21 ms 504 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 504 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 380 KB Output is correct
2 Correct 21 ms 1144 KB Output is correct
3 Correct 21 ms 1016 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 376 KB Output is correct
2 Correct 21 ms 1148 KB Output is correct
3 Correct 21 ms 1016 KB Output is correct