oj.uz

Submission #542607

# Submission time Handle Problem Language Result Execution time Memory
542607 2022-03-27T05:57:24 Z hollwo_pelw Towns (IOI15_towns) C++17
25 / 100
 15 ms 1108 KB 
#include "towns.h"

#include <bits/stdc++.h>
using namespace std;

namespace {

const int MAXN = 1 << 8;

struct query_dist {

	int d[MAXN][MAXN];

	inline void clear() {
		memset(d, -1, sizeof d);
		for (int i = 0; i < MAXN; i++)
			d[i][i] = 0;
	}

	inline int operator () (int x, int y) {
		if (d[x][y] == -1)
			d[x][y] = d[y][x] = getDistance(x, y);
		return d[x][y];
	}

} dist;

int hs[MAXN], ht[MAXN], cand[MAXN], pos[MAXN];

inline int same_branch(int u, int v) {
	if (pos[u] != pos[v] || cand[u] != cand[v]) return 0;
	// call at most (N + 1) / 2 times
	return (hs[u] + hs[v] - dist(u, v)) > (pos[u] << 1);
}

bool check(int N) {
	if (count(cand, cand + N, 1) == 0)
		return 0;

	vector<pair<int, int>> v;
	vector<int> st(1, 0);
	int cnt = 1;

	for (int i = 1; i < N; i++) {
		if (st.empty() || same_branch(st.back(), i)) {
			st.push_back(i);
			cnt ++;
		} else {
			int last = st.back();
			st.pop_back();

			v.emplace_back(i, 1);

			if (st.empty()) { // not dominator any more ?
				v.emplace_back(last, cnt);
				cnt = 0;
			}

		}
	}

	if (st.empty()) return 1; // no dominator

	int dominator = st.back();

	for (auto vp : v) {
		if (same_branch(vp.first, dominator))
			cnt += vp.second;
	}

	return cnt <= N / 2;
}

}

int hubDistance(int N, int sub) {
	dist.clear();

	for (int i = 0; i < N; i++)
		hs[i] = dist(0, i);

	int s = max_element(hs, hs + N) - hs;

	for (int i = 0; i < N; i++)
		hs[i] = dist(s, i);

	int t = max_element(hs, hs + N) - hs;

	for (int i = 0; i < N; i++)
		ht[i] = dist(t, i);

	const int diameter = dist(s, t);

	map<int, vector<int>> grp;

	int R = 1e9, last = 0;

	for (int i = 0; i < N; i++) {
		int p = (hs[i] - ht[i] + diameter) >> 1;

		pos[i] = p;
		grp[p].push_back(i);

		R = min(R, max(p, diameter - p));
	}

	if (sub <= 2) return R;

	memset(cand, 0, sizeof cand);

	int mn = 1e9;

	for (auto vp : grp) {
		vector<int> v = vp.second;
		int p = vp.first, n = v.size();

		if (max(p, diameter - p) == R && max(last, N - n - last) <= N / 2) {
			mn = min(mn, n);
			for (int u : v) cand[u] = 1;
		}
	}
	
	return mn <= N / 2 || check(N) ? R : - R;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:82:34: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   82 |  int s = max_element(hs, hs + N) - hs;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:87:34: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   87 |  int t = max_element(hs, hs + N) - hs;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:115:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  115 |   int p = vp.first, n = v.size();
      |                         ~~~~~~^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 852 KB Output is correct
2 Correct 10 ms 960 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 15 ms 1108 KB Output is correct
5 Correct 14 ms 1076 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 852 KB Output is correct
2 Correct 10 ms 1076 KB Output is correct
3 Correct 14 ms 1088 KB Output is correct
4 Correct 13 ms 1108 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -