Submission #103602

#	Time	Username	Problem	Language	Result	Execution time	Memory
103602		Lawliet	Towns (IOI15_towns)	C++14	35 / 100	22 ms	1264 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"

#define MAX 120
#define OO 1000000010
#define debug //printf

using namespace std;

int n;
int radius;
int diameter;
int qnt_hubs;
int d1, d2, d;

int cnt[5][5];
int dist[MAX][MAX];

vector<int> difference;
vector<int> acumulated;

/*int getDistance(int i, int j)
{
	printf("DIST %d e %d\n",i,j);
	
	int a;
	scanf("%d",&a);
	
	return a;
}*/

int get_all(int i)
{
	for(int g = 0 ; g < n ; g++)
		if(dist[g][i] == -1)
			dist[g][i] = dist[i][g] = getDistance(g , i);
}

int get_farthest(int i)
{
	int ans = i;
	
	for(int g = 0 ; g < n ; g++)
		if(dist[i][g] > dist[i][ans]) ans = g;
		
	return ans;
}

int divided_segment(int i, int j, int x)
{
	int aux = (dist[j][i] - dist[j][x] + dist[i][x])/2;
	
	return aux;
}

void get_radius()
{
	get_all(0);
	d1 = get_farthest(0);
	
	get_all(d1);
	d2 = get_farthest(d1);
	
	int divided = divided_segment(0 , d1 , d2); //onde o d2 cai nesse segmento inicial [0,d1]
	int segment = dist[0][d1]; //tamanho do segmento inicial inteiro
	
	diameter = dist[d1][d2]; //diametro da arvore
			
	for(int g = 0 ; g < n ; g++)
	{
		int cur = divided_segment(0 , d1 , g);
						
		if(cur < divided) continue;
		
		int r1 = segment - cur;
		int r2 = diameter - r1;
				
		int aux = max(r1 , r2);
						
		if(aux < radius) d = r1;
		
		radius = min(radius , aux);
	}
	
	if(diameter%2 == 0 && diameter/2 == d) return;
	
	for(int g = 0 ; g < n ; g++)
	{
		int cur = divided_segment(0 , d1 , g); //distancia do 0 ate onde o g cai no segmento 
						
		if(cur == diameter - d) qnt_hubs = 2;
	}
}

bool is_equal(int i, int j, int k)
{		
	int div1 = divided_segment(d1 , 0 , i);
	int div2 = divided_segment(d1 , 0 , j);
	
	//printf("div1 = %d   div2 = %d\n",div1,div2);
		
	if(div1 == k && div2 == k)
	{
		if(dist[i][j] == -1)
			dist[i][j] = dist[j][i] = getDistance(i , j);
		
		if(divided_segment(d1 , j , i) == k) return false;
		return true;
	}
	
	if(div1 >= k && div2 <= k) return false;
	if(div1 <= k && div2 >= k) return false;
	
	return true;
}

void add(int val, int c, int id)
{
	if(val > c) cnt[id][1]++;
	if(val < c) cnt[id][0]++; 
}

bool is_balanced()
{	
	int k;
	
	for(int g = 0 ; g < n ; g++)
	{
		int l = divided_segment(d1 , 0 , g);
		
		add(l , d , 0);
		add(l , diameter - d , 1);
	}

	debug("iniciais 0  d1 = %d  d2 = %d\n",d1,d2);
	
	debug("qnt = %d d = %d\n",qnt_hubs,d);
	
	bool aux[] = {true , (qnt_hubs == 2)};
	
	for(int g = 0 ; g < 2 ; g++)
			debug("%d %d\n",cnt[g][0],cnt[g][1]);
		
	for(int g = 0 ; g < 2 ; g++)
		for(int h = 0 ; h < 2 ; h++)
			aux[g] = aux[g] && (cnt[g][h] <= n/2);
			
	debug("aux   %d %d\n",aux[0],aux[1]);
			
	if(!aux[0] && !aux[1]) return false;
		
	if(!aux[0]) k = diameter - d;
	else k = d;
	
	debug("k = %d\n",k);
	
	difference.push_back(0);
	
	for(int g = 1 ; g < n ; g++)
	{
		bool equal = is_equal(difference.back() , g , k);
		
		debug("------------- g = %d   %d\n",g,difference.back());
				
		if(equal) acumulated.push_back(difference.back());
		else
		{
			difference.push_back(g);
			
			if(!acumulated.empty())
			{
				difference.push_back(acumulated.back());
				
				acumulated.pop_back();
			}
		}
		
		for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
		debug("\n");
		for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
		debug("\n");
	}
		
	int majoritary = difference.back();

	debug("majoritary = %d\n",majoritary);
		
	while( difference.size() > 1)
	{
		if(is_equal(majoritary , difference.back() , k)) difference.pop_back();
		else if(acumulated.empty()) return true;
		else acumulated.pop_back();
		
		difference.pop_back();

		debug("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\n");

		for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
		debug("\n");
		for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
		debug("\n");

	}
	
	if(difference.size() == 1)
	{
		if(is_equal(difference.back() , majoritary , k)) acumulated.push_back(majoritary);
		else if(acumulated.empty()) return true;
		else acumulated.pop_back();
	}
	
	return acumulated.empty();
}

void init()
{
	memset(dist , -1 , sizeof(dist));
	memset(cnt , 0 , sizeof(cnt));

	for(int g = 0 ; g < MAX ; g++) dist[g][g] = 0;
	
	radius = OO;
	qnt_hubs = 1;
	
	difference.clear();
	acumulated.clear();
}

int hubDistance(int N, int sub)
{
	n = N;
	
	init();
	
	get_radius();
	
	if(is_balanced()) return radius;
	return -radius;
}

/*int main()
{
	scanf("%d",&n);
	
	printf("%d\n",hubDistance(n, 0));
}*/

Compilation message (stderr)

towns.cpp: In function 'int get_all(int)':
towns.cpp:37:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
towns.cpp: In function 'bool is_balanced()':
towns.cpp:135:41: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("iniciais 0  d1 = %d  d2 = %d\n",d1,d2);
                                         ^~
towns.cpp:135:44: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("iniciais 0  d1 = %d  d2 = %d\n",d1,d2);
                                            ^~
towns.cpp:137:28: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("qnt = %d d = %d\n",qnt_hubs,d);
                            ^~~~~~~~
towns.cpp:137:37: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("qnt = %d d = %d\n",qnt_hubs,d);
                                     ^
towns.cpp:142:28: warning: left operand of comma operator has no effect [-Wunused-value]
    debug("%d %d\n",cnt[g][0],cnt[g][1]);
                            ^
towns.cpp:142:28: warning: right operand of comma operator has no effect [-Wunused-value]
    debug("%d %d\n",cnt[g][0],cnt[g][1]);
                    ~~~~~~~~^
towns.cpp:148:29: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("aux   %d %d\n",aux[0],aux[1]);
                             ^
towns.cpp:148:29: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("aux   %d %d\n",aux[0],aux[1]);
                        ~~~~~^
towns.cpp:155:19: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("k = %d\n",k);
                   ^
towns.cpp:163:39: warning: left operand of comma operator has no effect [-Wunused-value]
   debug("------------- g = %d   %d\n",g,difference.back());
                                       ^
towns.cpp:163:57: warning: right operand of comma operator has no effect [-Wunused-value]
   debug("------------- g = %d   %d\n",g,difference.back());
                                                         ^
towns.cpp:178:11: warning: declaration of 'k' shadows a previous local [-Wshadow]
   for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
           ^
towns.cpp:125:6: note: shadowed declaration is here
  int k;
      ^
towns.cpp:178:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
                   ~~^~~~~~~~~~~~~~~~~~~
towns.cpp:178:72: warning: left operand of comma operator has no effect [-Wunused-value]
   for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
                                                                        ^
towns.cpp:179:14: warning: statement has no effect [-Wunused-value]
   debug("\n");
              ^
towns.cpp:180:11: warning: declaration of 'k' shadows a previous local [-Wshadow]
   for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
           ^
towns.cpp:125:6: note: shadowed declaration is here
  int k;
      ^
towns.cpp:180:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
                   ~~^~~~~~~~~~~~~~~~~~~
towns.cpp:180:72: warning: left operand of comma operator has no effect [-Wunused-value]
   for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
                                                                        ^
towns.cpp:181:14: warning: statement has no effect [-Wunused-value]
   debug("\n");
              ^
towns.cpp:186:28: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("majoritary = %d\n",majoritary);
                            ^~~~~~~~~~
towns.cpp:196:70: warning: statement has no effect [-Wunused-value]
   debug("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\n");
                                                                      ^
towns.cpp:198:11: warning: declaration of 'k' shadows a previous local [-Wshadow]
   for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
           ^
towns.cpp:125:6: note: shadowed declaration is here
  int k;
      ^
towns.cpp:198:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
                   ~~^~~~~~~~~~~~~~~~~~~
towns.cpp:198:72: warning: left operand of comma operator has no effect [-Wunused-value]
   for(int k = 0 ; k < difference.size() ; k++) debug("%d ",difference[k]);
                                                                        ^
towns.cpp:199:14: warning: statement has no effect [-Wunused-value]
   debug("\n");
              ^
towns.cpp:200:11: warning: declaration of 'k' shadows a previous local [-Wshadow]
   for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
           ^
towns.cpp:125:6: note: shadowed declaration is here
  int k;
      ^
towns.cpp:200:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
                   ~~^~~~~~~~~~~~~~~~~~~
towns.cpp:200:72: warning: left operand of comma operator has no effect [-Wunused-value]
   for(int k = 0 ; k < acumulated.size() ; k++) debug("%d ",acumulated[k]);
                                                                        ^
towns.cpp:201:14: warning: statement has no effect [-Wunused-value]
   debug("\n");
              ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:229:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub)
                            ^~~

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