Submission #538366

#	Time	Username	Problem	Language	Result	Execution time	Memory
538366		NachoLibre	Towns (IOI15_towns)	C++17	0 / 100	15 ms	468 KiB

towns

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define vint vector<int>
using namespace std;
#ifndef x
#include "towns.h"
#else
int getDistance(int x, int y) {
	return 0;
}
#endif

map<array<int, 2>, int> ma;
int dist(int x, int y) {
	if(x == y) return 0;
	if(x > y) swap(x, y);
	if(!ma[{x, y}]) {
		ma[{x, y}] = getDistance(x, y);
	}
	return ma[{x, y}];
}

int s;

int hubDistance(int n, int sub) {
	if(sub > 2) assert(0);
	ma.clear();

	for(int i = 0, mx = 0; i < n; ++i) {
		if(dist(0, i) > mx) {
			mx = dist(0, i);
			s = i;
		}
	}

	int dm = 0;
	for(int i = 0; i < n; ++i) {
		dm = max(dm, dist(s, i));
	}

	vector<array<int, 2> > ytf;
	for(int i = 1; i < n; ++i) {
		if(i == s) continue;
		int al = dist(s, i) + dist(s, 0) - dist(0, i) >> 1;
		ytf.push_back({al, i});
	}
	vector<vector<int> > v;
	sort(all(ytf));
	int lmx = 0, rmn = 0;
	for(int i = 0; i < sz(ytf); ++i) {
		if(!i || ytf[i - 1][0] < ytf[i][0]) {
			v.push_back({});
			v.back().push_back(ytf[i][0]);
			if(ytf[i][0] <= dm / 2) lmx = ytf[i][0];
			else if(!rmn) rmn = ytf[i][0];
		}
		v.back().push_back(ytf[i][1]);
	}
	if(!rmn) rmn = lmx;
	else if(dm - lmx < rmn) rmn = lmx;
	else if(dm - lmx > rmn) lmx = rmn;
	int dr = rmn;
	return dr;
}

#ifdef x
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}
#endif

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:47:36: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   47 |   int al = dist(s, i) + dist(s, 0) - dist(0, i) >> 1;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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