oj.uz

Submission #96589

# Submission time Handle Problem Language Result Execution time Memory
96589 2019-02-10T11:21:41 Z streifi Towns (IOI15_towns) C++14
35 / 100
 28 ms 1080 KB 
#include "towns.h"
#include <vector>
#include <iostream>
using namespace std;

const int MAX_DIST = 1e6+5;

vector< vector<int> > mat;

int get_dist(int a, int b) {
	if (mat[a][b] == -1)
		return mat[a][b] = mat[b][a] = getDistance(a, b);
	else
		return mat[a][b];
}


int hubDistance(int N, int sub) {
	mat.assign(N, vector<int>(N, -1));
	int u = -1;
	int mx = -1;
	for (int i = 0; i < N; ++i) {
		if (get_dist(0, i) > mx) {
			u = i;
			mx = get_dist(0, i);
		}
	}
	int v = -1;
	mx = -1;
	for (int i = 0; i < N; ++i) {
		if (get_dist(u, i) > mx) {
			v = i;
			mx = get_dist(u, v);
		}
	}
	//cout << u << " " << v << endl;
	vector<int> freq(mx+1, 0);
	for (int i = 0; i < N; ++i) {
		int k = get_dist(i, u);
		int l = get_dist(i, v);
		++freq[(mx+k-l)/2];
	}
	int ans = 0x3f3f3f3f;
	bool bal; int cur = 0;
	for (int i = 0; i < mx; ++i) {
		//cout << freq[i] << " ";
		if (freq[i] && max(i, mx-i) <= ans) {

			if (max(i, mx-i) < ans) {
				ans = max(i, mx-i);
				bal = false;
			}
			if (!bal) {
				if (max(freq[i], max(cur, N-freq[i]-cur)) <= N/2) bal = true;
			}
			cur += freq[i];
		}
	}
	//cout << endl;
	if (!bal) ans *= -1;
	return ans;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:18:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) {
                            ^~~
towns.cpp:60:2: warning: 'bal' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (!bal) ans *= -1;
  ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 476 KB Output is correct
2 Correct 13 ms 504 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 19 ms 504 KB Output is correct
5 Correct 18 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 504 KB Output is correct
2 Correct 28 ms 548 KB Output is correct
3 Correct 18 ms 376 KB Output is correct
4 Correct 18 ms 376 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 39.0

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