Submission #767612

#	Time	Username	Problem	Language	Result	Execution time	Memory
767612		Cyber_Wolf	Towns (IOI15_towns)	C++17	13 / 100	13 ms	1108 KiB

towns

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

using namespace std;


#define lg long long

lg dist[200][200], r[200][200], q = 0;

lg d(lg x, lg y)
{
	if(x == y)	return 0;
	if(~dist[x][y])	return dist[x][y];
	q++;
	return dist[x][y] = dist[y][x] = getDistance(x, y);
}

int hubDistance(int N, int sub) 
{
	q = 0;
	for(int i = 0; i < N; i++)	for(int j = 0; j < N; j++)	dist[i][j] = -1;
	lg s = 0;
	for(int i = 1; i < N; i++)
	{
		if(d(s, 0) < d(i, 0))	s = i;
	}
	lg t = 0;
	for(int i = 1; i < N; i++)
	{
		if(d(t, s) < d(i, s))	t = i;
	}
	map<lg, vector<lg>> mp;
	lg ans = 1e18;
	for(int i = 0; i < N; i++)
	{
		lg dis = (d(s, t)-d(t, i)+d(i, s))/2;
		ans = min(ans, max(d(s, t)-dis, dis));
		mp[dis].push_back(i);
	}
	lg left = 0;
	for(auto [val, a] : mp)
	{
	    if(left > N/2 || N-left-a.size() > N/2) continue;
		if(ans == max(val, d(s, t)-val))	
		{
		    vector<vector<lg>> dead, alive;
    		for(auto it : a)	alive.push_back({it});
    		vector<lg> last;
    		while(alive.size())
    		{
    			vector<vector<lg>> new_v;
    			for(int i = 0; i < alive.size(); i += 2)
    			{
    				if(i+1 == alive.size())
    				{
    					if(last.size())	dead.push_back(last);
    					last = alive[i];
    					continue;
    				}
    				if(d(s, alive[i][0])+d(s, alive[i+1][0])-d(alive[i][0], alive[i+1][0]) > 2*val)
    				{
    					for(auto it : alive[i+1])	alive[i].push_back(it);
    					new_v.push_back(alive[i]);
    				}
    				else{
    					dead.push_back(alive[i]);
    					dead.push_back(alive[i+1]);
    				}
    			}
    			swap(alive, new_v);
    		}
    		if(last.empty())	return ans;
    		lg cnt = last.size();
    		for(auto it : dead)
    		{
    			if(d(s, it[0])+d(s, last[0])-d(last[0], it[0]) > 2*val)	cnt += it.size();
    		}
    		if(cnt <= N/2)	return ans;    
		}
		left += a.size();
	}
	return -ans;
}

Compilation message (stderr)

towns.cpp: In function 'long long int d(long long int, long long int)':
towns.cpp:16:47: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |  return dist[x][y] = dist[y][x] = getDistance(x, y);
      |                                               ^
towns.cpp:16:50: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   16 |  return dist[x][y] = dist[y][x] = getDistance(x, y);
      |                                                  ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:44:39: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   44 |      if(left > N/2 || N-left-a.size() > N/2) continue;
      |                       ~~~~~~~~~~~~~~~~^~~~~
towns.cpp:53:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |        for(int i = 0; i < alive.size(); i += 2)
      |                       ~~^~~~~~~~~~~~~~
towns.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if(i+1 == alive.size())
      |            ~~~~^~~~~~~~~~~~~~~
towns.cpp:73:31: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   73 |       if(last.empty()) return ans;
      |                               ^~~
towns.cpp:79:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   79 |       if(cnt <= N/2) return ans;
      |                             ^~~
towns.cpp:83:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |  return -ans;
      |         ^~~~
towns.cpp:19:28: warning: unused parameter 'sub' [-Wunused-parameter]
   19 | int hubDistance(int N, int sub)
      |                        ~~~~^~~

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