Submission #538654

#	Time	Username	Problem	Language	Result	Execution time	Memory
538654		NachoLibre	Towns (IOI15_towns)	C++17	100 / 100	27 ms	1068 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
vector<vint > formt(int m, vint v) {
	vector<vint > x;
	for(int i = 0; i < sz(v); ++i) {
		if(sz(x) == 0 || sz(x.back()) == m) x.push_back({});
		x.back().push_back(v[i]);
	}
	return x;
}

const int N = 102;
vector<array<int, 2> > v[N];
int dfsDist(int x, int y, int w = 0, int d = 0) {
	if(x == y) return d;
	for(auto z : v[x]) {
		if(z[0] == w) continue;
		int t = dfsDist(z[0], y, x, d + z[1]);
		if(t) return t;
	}
	return 0;
}
vector<vector<int> > distArch;
int getDistance(int x, int y) {
	if(0) return dfsDist(x, y);
	else return distArch[x][y];
}
#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 globz;
bool sameComponent(int x, int y) {
	return dist(s, x) + dist(s, y) - dist(x, y) >> 1 > globz;
}

int majC(vint v) {
	int cnt = 0;
	vint lst, bckt;
	for(int x : v) {
		if(!sz(lst) || !sameComponent(x, lst.back())) {
			lst.push_back(x);
			if(sz(bckt)) {
				lst.push_back(bckt.back());
				bckt.pop_back();
			}
		} else {
			bckt.push_back(x);
		}
	}
	int t = lst.back();
	while(sz(lst)) {
		if(sameComponent(t, lst.back())) {
			if(sz(lst) == 1) {
				bckt.push_back(lst.back());
				lst.pop_back();
			} else {
				lst.pop_back();
				cnt += 1;
				lst.pop_back();
			}
		} else {
			if(!sz(bckt)) return 0;
			bckt.pop_back();
			cnt += 1;
			lst.pop_back();
		}
	}
	if(!sz(bckt)) return 0;
	return cnt + sz(bckt);
}

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;
		}
	}
	// cout << "[s]: " << s << "\n";

	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]);
			// cout << "\n" << 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]);
		// cout << ytf[i][1] << " ";
	}
	if(!lmx) lmx = rmn;
	else if(!rmn) rmn = lmx;
	else if(dm - lmx < rmn) rmn = lmx;
	else if(dm - lmx > rmn) lmx = rmn;
	assert(lmx <= rmn);
	int dr = -max(lmx, dm - lmx);
	vint ftl(sz(v)), ftr(sz(v));
	if(sz(v) > 1) {
		ftl[1] = 1;
		ftr[sz(v) - 2] = 1;
	}
	for(int i = 1; i < sz(v); ++i) {
		ftl[i] += ftl[i - 1] + sz(v[i - 1]) - 1;
	}
	for(int i = sz(v) - 2; i >= 0; --i) {
		ftr[i] += ftr[i + 1] + sz(v[i + 1]) - 1;
	}
	// cout << lmx << " " << rmn << endl;
	for(int i = 0; i < sz(v); ++i) {
		// cout << v[i][0] << endl;
		if(v[i][0] == lmx || v[i][0] == rmn) {
			// cout << ftl[i] << ", " << ftr[i] << endl;
			if(ftl[i] > n / 2 || ftr[i] > n / 2) {
				continue;
			}
			globz = v[i][0];
			vector<int> t;
			for(int j = 1; j < sz(v[i]); ++j) {
				t.push_back(v[i][j]);
			}
			int x = majC(t);
			if(x <= n / 2) dr = abs(dr);
		}
	}
	return dr;
}

#ifdef x
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int sub, n;
	sub = 1;
	n = 11;
	distArch = formt(n, vint{
	0, 17, 18, 20, 17, 12, 20, 16, 23, 20, 11,
	17, 0, 23, 25, 22, 17, 25, 21, 28, 25, 16,
	18, 23, 0, 12, 21, 16, 24, 20, 27, 24, 17,
	20, 25, 12, 0, 23, 18, 26, 22, 29, 26, 19,
	17, 22, 21, 23, 0, 9, 21, 17, 26, 23, 16,
	12, 17, 16, 18, 9, 0, 16, 12, 21, 18, 11,
	20, 25, 24, 26, 21, 16, 0, 10, 29, 26, 19,
	16, 21, 20, 22, 17, 12, 10, 0, 25, 22, 15,
	23, 28, 27, 29, 26, 21, 29, 25, 0, 21, 22,
	20, 25, 24, 26, 23, 18, 26, 22, 21, 0, 19,
	11, 16, 17, 19, 16, 11, 19, 15, 22, 19, 0 });

	cout << hubDistance(n, sub) << endl;

	return 0;
}
#endif

Compilation message (stderr)

towns.cpp: In function 'bool sameComponent(int, int)':
towns.cpp:52:33: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   52 |  return dist(s, x) + dist(s, y) - dist(x, y) >> 1 > globz;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:111:36: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  111 |   int al = dist(s, i) + dist(s, 0) - dist(0, i) >> 1;
      |            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:91:28: warning: unused parameter 'sub' [-Wunused-parameter]
   91 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~

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