Submission #591009

#	Time	Username	Problem	Language	Result	Execution time	Memory
591009		AlperenT	Towns (IOI15_towns)	C++17	48 / 100	19 ms	888 KiB

towns

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

using namespace std;

const int N = 110, INF = 1e9 + 5;

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

	vector<int> childs;
	vector<pair<int, int>> childs2;
};

int dist[N][N];

struct DSU{
	int par[N], setsize[N];

	void reset(){
		for(int i = 0; i < N; i++) par[i] = i, setsize[i] = 1;
	}

	int setfind(int a){
		if(par[a] == a) return par[a];
		else return par[a] = setfind(par[a]);
	}

	void setunion(int a, int b){
		a = setfind(a), b = setfind(b);

		if(a != b){
			if(setsize[b] > setsize[a]) swap(a, b);

			par[b] = par[a];
			setsize[a] += setsize[b];
		}
	}
};

DSU dsu;

int hubDistance(int n, int sub){
	if(sub == 3){
		dsu.reset();
		
		for(int i = 0; i < n; i++){
			for(int j = i + 1; j < n; j++){
				dist[i][j] = dist[j][i] = getDistance(i, j);
			}
		}

		int A = max_element(dist[0], dist[0] + n) - dist[0];

		int B = max_element(dist[A], dist[A] + n) - dist[A];

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

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

			mp[{dist[A][C] - xtoc, dist[B][C] - xtoc}].push_back({xtoc, C});
		}

		int mn = INF;

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

		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].childs2.size();
		}

		sum = 0;

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

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

		vector<City> hubs;

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

		// cout << hubs.size() << "\n";

		for(auto hub : hubs){
			for(int i = 0; i < hub.childs2.size(); i++){
				for(int j = i + 1; j < hub.childs2.size(); j++){
					if(dist[hub.childs2[i].second][hub.childs2[j].second] != hub.childs2[i].first + hub.childs2[j].first){
						dsu.setunion(hub.childs2[i].second, hub.childs2[j].second);
					}
				}
			}

			int mx = 0;

			// cout << hub.adist << " " << hub.acnt << " " << hub.bdist << " " << hub.bcnt << "\n";

			// for(auto p : hub.childs2) cout << p.second << " " << dsu.setsize[dsu.setfind(p.second)] << "\n";

			for(auto p : hub.childs2) mx = max(mx, dsu.setsize[dsu.setfind(p.second)]);

			if(mx <= n / 2) return mn;
		}

		return -mn;
	}
	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:53:45: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   53 |   int A = max_element(dist[0], dist[0] + n) - dist[0];
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
towns.cpp:55:45: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   55 |   int B = max_element(dist[A], dist[A] + n) - dist[A];
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
towns.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<City>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int i = 0; i < cities.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~
towns.cpp:78:34: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   78 |    sum += cities[i].childs2.size();
      |                                  ^
towns.cpp:83:29: warning: conversion from 'std::vector<City>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   83 |   for(int i = cities.size() - 1; i >= 0; i--){
      |               ~~~~~~~~~~~~~~^~~
towns.cpp:86:34: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   86 |    sum += cities[i].childs2.size();
      |                                  ^
towns.cpp:100:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |    for(int i = 0; i < hub.childs2.size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~
towns.cpp:101:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int j = i + 1; j < hub.childs2.size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~
towns.cpp:126:41: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  126 |   int A = max_element(dist0, dist0 + n) - dist0;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
towns.cpp:132:41: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  132 |   int B = max_element(distA, distA + n) - distA;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
towns.cpp:158:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<City>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |    for(int i = 0; i < cities.size(); i++){
      |                   ~~^~~~~~~~~~~~~~~
towns.cpp:161:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  161 |     sum += cities[i].childs.size();
      |                                  ^
towns.cpp:166:30: warning: conversion from 'std::vector<City>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  166 |    for(int i = cities.size() - 1; i >= 0; i--){
      |                ~~~~~~~~~~~~~~^~~
towns.cpp:169:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  169 |     sum += cities[i].childs.size();
      |                                  ^
towns.cpp:173:103: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  173 |     if(max(cty.adist, cty.bdist) == mn && cty.acnt <= n / 2 && cty.bcnt <= n / 2 && cty.childs.size() <= n / 2) return mn;
      |                                                                                     ~~~~~~~~~~~~~~~~~~^~~~~~~~

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