oj.uz

Submission #127541

# Submission time Handle Problem Language Result Execution time Memory
127541 2019-07-09T14:32:09 Z kingfran1907 Towns (IOI15_towns) C++14
100 / 100
 21 ms 1156 KB 
#include "towns.h"
#include <bits/stdc++.h>

using namespace std;
const int maxn = 150;
const int inf = 0x3f3f3f3f;

int qs[maxn][maxn];
int deb = 0;

int n;
int query(int a, int b) {
	assert(a < n && b < n && a >= 0 && b >= 0);
	if (a > b) swap(a, b);
	if (qs[a][b] == -1) qs[a][b] = getDistance(a, b);
	return qs[a][b];
}

int a, b;
int B;
bool subtree(int x, int y) {
	int xd = (query(a, x) + query(b, x) - query(a, b)) / 2;
	int yd = (query(a, y) + query(b, y) - query(a, b)) / 2;
	return (xd + yd) > query(x, y);
}

int hubDistance(int n, int sub) {
	deb++;
	//for (int i = 0; i < n * n; i++) getdistance(0, 1);
	::n = n;
	memset(qs, -1, sizeof qs);
	a = b = B = 0;
	//memset(sol, inf, sizeof sol);

	for (int i = 0; i < n; i++)
		qs[i][i] = 0;

	a = 0, b = 0;
	for (int i = 0; i < n; i++)
		if (query(0, a) < query(0, i)) a = i;

	for (int i = 0; i < n; i++)
		if (query(a, b) < query(a, i)) b = i;
	
	B = b; b = 0;
	int hu = -1, out = inf;
	for (int i = 0; i < n; i++) {
		int cd = (query(a, i) + query(b, i) - query(a, b)) / 2;
		int ad = query(a, i) - cd;
		int bd = query(a, B) - ad;

		if (out > max(ad, bd)) out = max(ad, bd), hu = ad;
	}
	assert(hu > -1);

	int lef = 0, rig = 0;
	vector<int> v;
	for (int i = 0; i < n; i++) {
		int cd = (query(a, i) + query(b, i) - query(a, b)) / 2;
		int ad = query(a, i) - cd;

		if (ad < hu) lef++;
		else if (ad > hu) rig++;
		else v.push_back(i);
	}
	if (max(lef, rig) > n / 2) {
		//cerr << "not sure: " << deb << " - " << lef << " " << rig << " (" << n << ")" << endl;
		hu = query(a, B) - hu;
		//cerr << "diametar: " << deb << " - " << query(a, B) << endl;

		int lef = 0, rig = 0;
		vector<int> v;
		for (int i = 0; i < n; i++) {
			int cd = (query(a, i) + query(b, i) - query(a, b)) / 2;
			int ad = query(a, i) - cd;

			if (ad < hu) lef++;
			else if (ad > hu) rig++;
			else v.push_back(i);
		}

		//cerr << "new status: " << deb << " - " << lef << " " << rig << " (" << n << ")" << endl;
		if (max(lef, rig) > n / 2) return -out;
	}
	if (v.size() == 0) {
		//cerr << "v = 0: " << deb << endl;
		if (max(lef, rig) > n / 2) return -out;
		else return out;
	}

	vector<int> li, buk;
	li.push_back(v[0]);
	for (int i = 1; i < v.size(); i++) {
		if (subtree(v[i], li.back())) buk.push_back(v[i]);
		else {
			li.push_back(v[i]);
			if (!buk.empty()) {
				li.push_back(buk.back());
				buk.pop_back();
			}
		}
	}

	int cnt = 0;
	int kan = li.back();
	//cerr << "ph: " << deb << endl;
	while (li.size() > 0) {
		if (subtree(li.back(), kan)) {
			if (li.size() == 1) {
				buk.push_back(li.back());
				li.pop_back();
			} else {
				li.pop_back();
				li.pop_back();
				cnt++;
			}
		} else {
			if (buk.empty()) return out;
			else {
				li.pop_back();
				buk.pop_back();
				cnt++;
			}
		}
	}

	cnt += buk.size();
	//cerr << "debug: " << deb << " -> " << cnt << endl;
	if (cnt > n / 2) return -out;
	else return out;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:27:31: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 int hubDistance(int n, int sub) {
                               ^
towns.cpp:11:5: note: shadowed declaration is here
 int n;
     ^
towns.cpp:71:7: warning: declaration of 'lef' shadows a previous local [-Wshadow]
   int lef = 0, rig = 0;
       ^~~
towns.cpp:56:6: note: shadowed declaration is here
  int lef = 0, rig = 0;
      ^~~
towns.cpp:71:16: warning: declaration of 'rig' shadows a previous local [-Wshadow]
   int lef = 0, rig = 0;
                ^~~
towns.cpp:56:15: note: shadowed declaration is here
  int lef = 0, rig = 0;
               ^~~
towns.cpp:72:15: warning: declaration of 'v' shadows a previous local [-Wshadow]
   vector<int> v;
               ^
towns.cpp:57:14: note: shadowed declaration is here
  vector<int> v;
              ^
towns.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < v.size(); i++) {
                  ~~^~~~~~~~~~
towns.cpp:127:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  cnt += buk.size();
                  ^
towns.cpp:27:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int n, int sub) {
                            ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1028 KB Output is correct
2 Correct 16 ms 888 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 21 ms 1016 KB Output is correct
5 Correct 21 ms 1144 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 504 KB Output is correct
2 Correct 16 ms 888 KB Output is correct
3 Correct 21 ms 1016 KB Output is correct
4 Correct 21 ms 1020 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 888 KB Output is correct
2 Correct 21 ms 1144 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 21 ms 1016 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 536 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 508 KB Output is correct
2 Correct 21 ms 1156 KB Output is correct
3 Correct 21 ms 1016 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 504 KB Output is correct
2 Correct 21 ms 1144 KB Output is correct
3 Correct 21 ms 1016 KB Output is correct