Submission #590987

#	Time	Username	Problem	Language	Result	Execution time	Memory
590987		AlperenT	Towns (IOI15_towns)	C++17	35 / 100	18 ms	356 KiB

towns

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

using namespace std;

const int INF = 1e9 + 5;

struct City{
	int adist, bdist, acnt, bcnt;

	vector<int> childs;
};

int hubDistance(int n, int sub){
	if(sub == 3){

	}
	else{
		int dist0[n];

		for(int i = 0; i < n; i++) dist0[i] = getDistance(0, i);

		int A = max_element(dist0, dist0 + n) - dist0;

		int distA[n];

		for(int i = 0; i < n; i++) distA[i] = getDistance(A, i);

		int B = max_element(distA, distA + n) - distA;

		int distB[n];

		for(int i = 0; i < n; i++) distB[i] = getDistance(B, i);

		map<pair<int, int>, vector<int>> mp;

		for(int C = 0; C < n; C++){
			int xtoc = (distA[C] + distB[C] - distA[B]) / 2;

			mp[{distA[C] - xtoc, distB[C] - xtoc}].push_back(xtoc);
		}

		int mn = INF;

		for(auto p : mp) mn = min(mn, max(p.first.first, p.first.second));

		if(sub == 1 || sub == 2) return mn;
		else if(sub == 4){
			vector<City> cities;

			for(auto p : mp) cities.push_back({p.first.first, p.first.second, 0, 0, p.second});

			int sum = 0;

			for(int i = 0; i < cities.size(); i++){
				cities[i].acnt = sum;

				sum += cities[i].childs.size();
			}

			sum = 0;

			for(int i = cities.size() - 1; i >= 0; i--){
				cities[i].bcnt = sum;

				sum += cities[i].childs.size();
			}

			for(auto cty : cities){
				if(max(cty.adist, cty.bdist) == mn && cty.acnt <= n / 2 && cty.bcnt <= n / 2 && cty.childs.size() <= n / 2) return mn;
			}

			return -mn;
		}
		else return -1;
	}
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:23:41: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   23 |   int A = max_element(dist0, dist0 + n) - dist0;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
towns.cpp:29:41: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   29 |   int B = max_element(distA, distA + n) - distA;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
towns.cpp:55:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<City>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for(int i = 0; i < cities.size(); i++){
      |                   ~~^~~~~~~~~~~~~~~
towns.cpp:58:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   58 |     sum += cities[i].childs.size();
      |                                  ^
towns.cpp:63:30: warning: conversion from 'std::vector<City>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   63 |    for(int i = cities.size() - 1; i >= 0; i--){
      |                ~~~~~~~~~~~~~~^~~
towns.cpp:66:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   66 |     sum += cities[i].childs.size();
      |                                  ^
towns.cpp:70:103: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |     if(max(cty.adist, cty.bdist) == mn && cty.acnt <= n / 2 && cty.bcnt <= n / 2 && cty.childs.size() <= n / 2) return mn;
      |                                                                                     ~~~~~~~~~~~~~~~~~~^~~~~~~~
towns.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
   77 | }
      | ^

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