Submission #52074

#	Time	Username	Problem	Language	Result	Execution time	Memory
52074		kingpig9	Towns (IOI15_towns)	C++11	0 / 100	3 ms	996 KiB

towns

//cleaner version of townsNo10.cpp. Version to submit.
#include <bits/stdc++.h>
#include "towns.h"
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 115;
 
//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
 
#warning There can be more than one test case. Make sure you reset at every level.
 
template<class T>
void setmin (T &a, T b) {
	if (b < a) {
		a = b;
	}
}
 
template<class T>
void setmax (T &a, T b) {
	if (a < b) {
		a = b;
	}
}
 
int N;
int subtask;
int dist[MAXN][MAXN];
 
int getdist (int x, int y) {
	assert(0 <= x);
	assert(x < N);
	assert(0 <= y);
	assert(y < N);
 
	if (x == y) {
		return 0;
	}
 
	if (x > y) {
		swap(x, y);
	}
 
	int &ref = dist[x][y];
	if (ref) {
		return ref;
	}
	return ref = getDistance(x, y);
}
 
array<int, 3> getcent (int a, int b, int c) {
	//get distance to the meeting place of a, b, c
	int dab = getdist(a, b), dac = getdist(a, c), dbc = getdist(b, c);
	return array<int, 3> {(dab + dac - dbc) / 2, (dab - dac + dbc) / 2, (-dab + dac + dbc) / 2};
}
 
int diamx, diamy, diam;
int dxcent;
int ans;
map<int, vector<int>> mp;
map<int, int> psum, ssum;	//prefix sum, suffix sum
 
void reset() {
	fillchar(dist, 0);
	diamx = diam = ans = 0;
	mp.clear();
	psum.clear();
}
 
bool has_balanced_hub() {
	for (auto it : mp) {
		//check if hub
		int dl = it.fi;
		if (dl > dxcent) {
			break;
		}

		int dr = diam - dl;
		if (dl == 0 || dr == 0) {
			continue;
		}
 
		if (max(dl, dr) == ans) {
			//this is a hub
			auto pit = prev(psum.find(dl));
			auto sit = next(ssum.find(dl));
			vector<int> leaves = it.se;
			/*
			debug("DIST %d:", dl);
			for (int leaf : leaves) {
				debug(" %d", leaf);
			}
			debug("\n");
			*/
			int lsize = pit->se;
			int csize = leaves.size();
			int rsize = N - lsize - csize;
			assert(rsize == sit->se);
			debug("lsize = %d, csize = %d, rsize = %d\n", lsize, csize, rsize);
 
			if (lsize > N / 2 || rsize > N / 2) {
				continue;
			}
			if (csize <= N / 2) {
				return true;
			}
			//dumb asserts -- primarily for reassurance
			assert(lsize <= N / 2);
			assert(rsize <= N / 2);
			assert(csize > N / 2);
 
			//otherwise - majority element!
			vector<int> vlist, bucket;
			for (int leaf : leaves) {
				if (vlist.empty() || getcent(diamx, vlist.back(), leaf)[0] == dl) {
					//not equal
					debug("noigual\n");
					vlist.push_back(leaf);
					if (!bucket.empty()) {
						vlist.push_back(bucket.back());
						bucket.pop_back();
					}
				} else {
					debug("siigual\n");
					//equal
					bucket.push_back(leaf);
				}
			}
 
			//check now whether it is a majority element
			//More formally: "maj" = potential majority element. Nothing else could be a majority element. Check its count.
			int maj = vlist.back();	//majority element

			while (!vlist.empty()) {
				int leaf = vlist.back();
				if (getcent(diamx, maj, leaf)[0] == dl) {
					//not equal
					if (bucket.empty()) {
						return true;
					}

					bucket.pop_back();
					vlist.pop_back();
				} else {
					//equal
					if (vlist.size() == 1) {
						bucket.push_back(vlist[0]);
						vlist.pop_back();
					} else {
						vlist.pop_back();
						vlist.pop_back();
					}
				}
			}
 
 			if (bucket.empty()) {
				return true;
			}
		}
	}
	return false;
}
 
pii getfar (int x) {
	//farthest away
	pii res(0, x);
	for (int i = 0; i < N; i++) {
		setmax(res, pii(getdist(i, x), i));
	}
	return res;
}

int go() {
	pii far0 = getfar(0);
	pii farx = getfar(far0.se);
	diamx = far0.se;
	diamy = farx.se;	//don't actually use this for querying.
	diam = farx.fi;
	debug("diameter: %d -> %d, distance %d\n", diamx, diamy, diam);
 
	ans = diam;
	dxcent = getcent(diamx, 0, diamy)[0];
	debug("distance from diamx = %d to CENTER is %d\n", diamx, dxcent);
	
	//note that this starts at ONE, not 0.
	for (int i = 0; i < N; i++) {
		int d = getcent(diamx, 0, i)[0];
		mp[d].push_back(i);
		setmin(ans, max(d, diam - d));
	}

	for (auto it = mp.begin(); it != mp.end(); it++) {
		psum[it->fi] = it->se.size();
		if (it != mp.begin()) {
			psum[it->fi] += psum[prev(it)->fi];
		}
	}
	for (auto it = mp.rbegin(); it != mp.rend(); it++) {
		ssum[it->fi] = it->se.size();
		if (it != mp.rbegin()) {
			ssum[it->fi] += ssum[prev(it)->fi];
		}
	}
 
	return has_balanced_hub() ? ans : -ans;
}
 
int hubDistance (int nnn, int subbbb) {
#warning reset totally global variables
	N = nnn;
	subtask = subbbb;
	reset();
	return go();
}

Compilation message (stderr)

towns.cpp:18:2: warning: #warning There can be more than one test case. Make sure you reset at every level. [-Wcpp]
 #warning There can be more than one test case. Make sure you reset at every level.
  ^~~~~~~
towns.cpp:217:2: warning: #warning reset totally global variables [-Wcpp]
 #warning reset totally global variables
  ^~~~~~~
towns.cpp: In function 'bool has_balanced_hub()':
towns.cpp:104:27: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
    int csize = leaves.size();
                ~~~~~~~~~~~^~
towns.cpp: In function 'int go()':
towns.cpp:201:29: warning: conversion to 'std::map<int, int>::mapped_type {aka int}' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   psum[it->fi] = it->se.size();
                  ~~~~~~~~~~~^~
towns.cpp:207:29: warning: conversion to 'std::map<int, int>::mapped_type {aka int}' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   ssum[it->fi] = it->se.size();
                  ~~~~~~~~~~~^~

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