oj.uz

Submission #383901

# Submission time Handle Problem Language Result Execution time Memory
383901 2021-03-31T01:03:56 Z LucaDantas Towns (IOI15_towns) C++17
100 / 100
 24 ms 1260 KB 
#include "towns.h"
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <vector>
#include <map>
 
constexpr int maxn = 300;
 
int dp[maxn][maxn], c[maxn];

std::map<int, std::vector<int>> filhos;
 
int get(int i, int j) {
	if(i > j) std::swap(i, j);
	return dp[i][j] != -1 ? dp[i][j] : dp[i][j] = getDistance(i, j);
}

int hubDistance(int N, int sub) {
	memset(dp, -1, sizeof dp);
	memset(c, 0, sizeof c);
	filhos.clear();
	int a = 0, b = 0, dist = 0;
	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < N; j++) {
			if(a != j) {
				int v = get(a, j);
				if(v > dist) b = j, dist = v;
			}
		}
		if(!i) std::swap(a, b);
	}
	b = 0;
	int R = 0x3f3f3f3f;
	for(int i = 0; i < N; i++) {
		if(i == a || i == b) continue;
		int d1 = get(a, i), d2 = get(b, i);
		c[i] = (d1 + d2 - get(a, b)) >> 1;
		R = std::min(R, std::max(d1 - c[i], dist - d1 + c[i]));
		filhos[d1-c[i]].push_back(i);
	}

	std::vector<int> lista, bucket;

	int sz = 1;
	for(auto it : filhos) {
		if(it.first != R && it.first != dist - R) {
			sz += (int)(it.second).size();
			continue;
		}
		if(sz > (N >> 1) || N - sz - (int)(it.second).size() > (N >> 1)) continue;
		std::vector<int> v = (it.second);
		int n = (int)v.size(); sz += n;
		if(n <= (N >> 1)) return R;
		for(int i = 0; i < n; i++) {
			if(!lista.size() || get(v[i], lista.back()) == c[v[i]] + c[lista.back()]) {
				lista.push_back(v[i]);
				if(bucket.size()) lista.push_back(bucket.back()),
				bucket.pop_back();
			}
			else bucket.push_back(v[i]);
		}
		// puts("lista");
		// for(int x : lista)
		// 	printf("%d\n", x);
		// puts("bucket");
		// for(int x : bucket)
		// 	printf("%d\n", x);
		int pivo = lista.back(), cnt = (int)bucket.size();
		while(lista.size()) {
			if(cnt > (N >> 1)) break;
			if(get(pivo, lista.back()) == c[lista.back()] + c[pivo]) {
				lista.pop_back();
				if(bucket.size()) bucket.pop_back();
			}
			else {
				++cnt;
				lista.pop_back();
				if(lista.size()) lista.pop_back();
			}
		}
		// puts("bucket");
		// for(int x : bucket)
		// 	printf("%d\n", x);
		if(cnt <= (N >> 1)) return R;
		// sz += n;
		// lista.clear();
		// bucket.clear();
	}

	return -R;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:20:28: warning: unused parameter 'sub' [-Wunused-parameter]
   20 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 748 KB Output is correct
2 Correct 15 ms 748 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 22 ms 748 KB Output is correct
5 Correct 23 ms 748 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 748 KB Output is correct
2 Correct 16 ms 748 KB Output is correct
3 Correct 21 ms 748 KB Output is correct
4 Correct 21 ms 748 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 748 KB Output is correct
2 Correct 21 ms 748 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 23 ms 748 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 876 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 876 KB Output is correct
2 Correct 22 ms 1260 KB Output is correct
3 Correct 22 ms 1260 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 748 KB Output is correct
2 Correct 21 ms 1260 KB Output is correct
3 Correct 24 ms 1260 KB Output is correct