oj.uz

답안 #51932

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51932 2018-06-22T16:35:20 Z kingpig9 도시들 (IOI15_towns) C++11
61 / 100
 40 ms 9140 KB 
#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;
const int INF = 1e9;

//#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};
}

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;
}

pair<int, pii> getdiam() {
	int diamx = getfar(0).se;
	pii farx = getfar(diamx);
	return make_pair(farx.fi, pii(diamx, farx.se));
}

int diamx, diamy, diam;
int ans;
map<int, vector<int>> mp;
map<int, int> psum, ssum;	//prefix sum, suffix sum

void reset() {
	fillchar(dist, 0);
	diamx = diamy = diam = ans = 0;
	mp.clear();
	psum.clear();
	ssum.clear();
}

bool has_balanced_hub() {
	for (auto it : mp) {
		//check if hub
		int dl = it.fi, 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));
			int lsize = pit->se;
			int rsize = sit->se;

			//debug("dl = %d, dr = %d. lsize = %d, rsize = %d. csize = %d.\n", dl, dr, lsize, rsize, csize);
			if (lsize > N / 2 || rsize > N / 2) {
				continue;
			}

			vector<int> leaves = it.se;
			int csize = leaves.size();
			if (csize <= N / 2) {
				return true;
			}

			if (subtask == 4) {
				//solves subtask 4 -- don't need to check anything else.
				continue;
			}

			//dumb asserts -- primarily for reassurance
			assert(lsize <= N / 2);
			assert(rsize <= N / 2);
			assert(csize > N / 2);

			//otherwise - majority element!
			int maj = -1, cnt = 0;
			for (int leaf : leaves) {
				if (cnt == 0) {
					maj = leaf;
					cnt = 1;	//is this really it?
					continue;
				}

				auto cen = getcent(diamx, maj, leaf);
				//had bug here: (cen[0] == lsize) supposed to be (cen[0] == dl). exactly the same bug appeared in a later line.
				if (cen[0] == dl) {
					//not equal
					cnt--;
				} else {
					//equal
					cnt++;
				}
			}

			assert(maj != -1);

			//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 sz = 0;
			for (int leaf : leaves) {
				if (leaf == maj) {
					sz++;
					continue;
				}

				auto cen = getcent(diamx, maj, leaf);
				//had bug here: (cen[0] == lsize) supposed to be (cen[0] == dl). exactly the same bug appeared in an earlier line.
				if (cen[0] != dl) {
					sz++;
				}
			}

			if (sz <= N / 2) {
				return true;
			}
		}
	}
	return false;
}

int go() {
	pair<int, pii> diamdata = getdiam();
	diamx = diamdata.se.fi;
	diamy = diamdata.se.se;
	diam = diamdata.fi;
	//debug("diameter: %d -> %d, distance %d\n", diamx, diamy, diam);

	ans = INF;
	mp = {{0, {diamx}}, {diam, {diamy}}};
	
	for (int i = 0; i < N; i++) {
		if (i != diamx && i != diamy) {
			auto cen = getcent(i, diamx, diamy);
			int fardist = max(cen[1], cen[2]);
			//debug("i = %d. fardist = %d\n", i, fardist);
			assert(fardist == max({cen[0], cen[1], cen[2]}));
			setmin(ans, fardist);
			assert(cen[1] + cen[2] == diam);
			mp[cen[1]].push_back(i);
		}
	}

	if (subtask <= 2) {
		//no need for balanced hub - solves subtasks 1 and 2
		return ans;
	}

	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

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:220:2: warning: #warning reset totally global variables [-Wcpp]
 #warning reset totally global variables
  ^~~~~~~
towns.cpp: In function 'bool has_balanced_hub()':
towns.cpp:114: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:204: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:210: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
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 1020 KB Output is correct
2 Correct 21 ms 1608 KB Output is correct
3 Correct 2 ms 1608 KB Output is correct
4 Correct 26 ms 2212 KB Output is correct
5 Correct 30 ms 2760 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 3480 KB Output is correct
2 Correct 22 ms 3912 KB Output is correct
3 Correct 23 ms 4428 KB Output is correct
4 Correct 26 ms 4964 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 5628 KB Output is correct
2 Correct 23 ms 6316 KB Output is correct
3 Correct 2 ms 6316 KB Output is correct
4 Correct 23 ms 6824 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 7540 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 8032 KB Output is correct
2 Correct 25 ms 8488 KB Output is correct
3 Correct 40 ms 9140 KB Output is correct

Subtask #6
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 9140 KB Output isn't correct
2 Halted 0 ms 0 KB -