oj.uz

Submission #802156

# Submission time Handle Problem Language Result Execution time Memory
802156 2023-08-02T10:29:49 Z prvocislo Towns (IOI15_towns) C++17
100 / 100
 20 ms 912 KB 
#pragma once
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

int getDistance(int i, int j);
map<pair<int, int>, int> got;
int getd(int i, int j)
{
	if (i > j) swap(i, j);
	if (got.count({ i, j })) return got[{i, j}];
	return got[{i, j}] = getDistance(i, j);
}

vector<int> p;
int root(int a) { return p[a] == a ? a : p[a] = root(p[a]); }
bool merge(int a, int b)
{
	a = root(a), b = root(b);
	if (a == b) return false;
	p[a] = b;
	return true;
}
int hubDistance(int N, int sub)
{
	p.resize(N);
	for (int i = 0; i < N; i++) p[i] = i;
	int a = 0, b = 0; got.clear();
	vector<int> d0(N, 0);
	for (int i = 0; i < N; i++) d0[i] = getd(0, i);
	a = max_element(d0.begin(), d0.end()) - d0.begin();
	vector<int> da(N, 0);
	for (int i = 0; i < N; i++) da[i] = getd(a, i);
	b = max_element(da.begin(), da.end()) - da.begin();
	// lets gooo, a -- b je diagonala
	int d = da[b], r = d;
	vector<pair<int, int> > v;
	for (int i = 0; i < N; i++) 
	{
		int dia;
		if (i)
		{
			int c = (da[i] + d0[i] - d0[a]) / 2;
			dia = da[i] - c;
		}
		else
		{
			int c = (d0[a] + d0[b] - d) / 2;
			dia = da[i] - c;
		}
		if (i != a && i != b) r = min(r, max(dia, d - dia));

		int c = (da[i] + d0[i] - d0[a]) / 2;
		if (i != 0 && i != a) v.push_back({ da[i] - c, i });
		if (i == 0) v.push_back({ d0[a], 0 });
		if (i == a) v.push_back({ 0, a });
	}
	int maxi = (da[0] + da[b] - d0[b]) / 2;
	int T = N / 2;
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) if ((!i || v[i-1].first != v[i].first) && (v[i].first == r || v[i].first == d - r) && v[i].first <= maxi)
	{
		int pv = 0, nx = 0;
		vector<int> cur;
		for (int j = 0; j < v.size(); j++)
		{
			if (v[j].first < v[i].first) pv++;
			if (v[j].first == v[i].first) cur.push_back(v[j].second);
			if (v[j].first > v[i].first) nx++;
		}
		if (pv > T || nx > T) continue;
		if (cur.size() <= T) return r;

		int vr = -1, num = 0;
		for (int j : cur)
		{
			if (num == 0) vr = j, num = 1;
			else
			{
				int q = da[vr] + d0[j] - da[0] - getd(vr, j);
				if (q) merge(vr, j), num++; // rovnaky podstrom
				else num--;
			}
		}
		vector<int> tr;
		for (int j : cur) 
			if (root(vr) != j && j == root(j)) tr.push_back(j);
		for (int j : tr)
		{
			int q = da[vr] + d0[j] - da[0] - getd(vr, j);
			if (q) merge(vr, j);
		}
		int cnt = 0;
		for (int j : cur) if (root(j) == root(vr)) cnt++;
		if (cnt <= T) return r;
	}
	return -r;
}

Compilation message

towns.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:38:40: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   38 |  a = max_element(d0.begin(), d0.end()) - d0.begin();
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:41:40: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   41 |  b = max_element(da.begin(), da.end()) - da.begin();
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for (int i = 0; i < v.size(); i++) if ((!i || v[i-1].first != v[i].first) && (v[i].first == r || v[i].first == d - r) && v[i].first <= maxi)
      |                  ~~^~~~~~~~~~
towns.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for (int j = 0; j < v.size(); j++)
      |                   ~~^~~~~~~~~~
towns.cpp:79:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |   if (cur.size() <= T) return r;
      |       ~~~~~~~~~~~^~~~
towns.cpp:31:28: warning: unused parameter 'sub' [-Wunused-parameter]
   31 | int hubDistance(int N, int sub)
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 364 KB Output is correct
2 Correct 13 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 12 ms 340 KB Output is correct
5 Correct 13 ms 368 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 9 ms 340 KB Output is correct
3 Correct 12 ms 368 KB Output is correct
4 Correct 20 ms 368 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 13 ms 872 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 872 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 372 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 20 ms 816 KB Output is correct
3 Correct 12 ms 912 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 376 KB Output is correct
2 Correct 14 ms 824 KB Output is correct
3 Correct 19 ms 896 KB Output is correct