oj.uz

Submission #115653

# Submission time Handle Problem Language Result Execution time Memory
115653 2019-06-08T12:34:51 Z E869120 Towns (IOI15_towns) C++14
61 / 100
 20 ms 1048 KB 
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

int N, dist[183][179];

int getdist(int u, int v) {
	if (u == v) return 0;
	if (dist[u][v] >= 1) return dist[u][v] - 1;
	
	int R = getDistance(u, v);
	dist[u][v] = R + 1; dist[v][u] = R + 1;
	return R;
}

pair<int, int> Furthest(int pos) {
	int maxn = -1, maxid = -1;
	for (int i = 0; i < N; i++) {
		int D = getdist(pos, i);
		if (D > maxn) { maxn = D; maxid = i; }
	}
	return make_pair(maxn, maxid);
}

bool isdifferent(int root, int dst, int u1, int u2) {
	int V1 = getdist(root, u1); V1 -= dst;
	int V2 = getdist(root, u2); V2 -= dst;
	int V3 = getdist(u1, u2);
	if (V1 + V2 == V3) return true;
	return false;
}

int exact_size(int root, int dst, vector<int> vec) {
	vector<int> vec2 = vec; int last = -1;
	while (vec2.size() >= 2) {
		vector<int> vec3;
		for (int i = 0; i < (int)vec2.size() - 1; i += 2) {
			bool I = isdifferent(root, dst, vec2[i], vec2[i + 1]);
			if (I == false) vec3.push_back(vec2[i]);
		}
		if (vec2.size() % 2 == 1) last = vec2[vec2.size() - 1];
		vec2 = vec3;
	}
	
	int C = last; if (vec2.size() >= 1) C = vec2[0];
	if (C == -1) return 1;
	
	int cnt = 0;
	for (int i = 0; i < vec.size(); i++) {
		bool I = isdifferent(root, dst, C, vec[i]);
		if (I == false) cnt++;
	}
	return cnt;
}

int hubDistance(int NN, int sub) {
	for (int i = 0; i < NN * NN; i++) dist[i / NN][i % NN] = 0;
	N = NN;
	pair<int, int> E1 = Furthest(0);
	pair<int, int> E2 = Furthest(E1.second);
	
	int diameter = E2.first, u1 = E1.second, u2 = E2.second, minx = (1 << 30);
	for (int i = 0; i < N; i++) {
		minx = min(minx, abs(getdist(u1, i) - getdist(u2, i)));
	}
		
	vector<int> t[4];
	for (int i = 0; i < N; i++) {
		int V1 = getdist(u1, i);
		int V2 = getdist(u2, i);
		if (V1 < V2) {
			if (abs(V1 - V2) == minx) t[1].push_back(i);
			else t[0].push_back(i);
		}
		if (V1 >= V2) {
			if (abs(V1 - V2) == minx) t[2].push_back(i);
			else t[3].push_back(i);
		}
	}
	
	int E[4] = {(int)t[0].size(), (int)t[1].size(), (int)t[2].size(), (int)t[3].size()};
	
	if (sub == 3 || sub == 5) {
		if (t[1].size() > N / 2) { int s = (getdist(u1, u2) + getdist(u1, t[1][0]) - getdist(u2, t[1][0])) / 2; E[1] = exact_size(u1, s, t[1]); }
		if (t[2].size() > N / 2) { int s = (getdist(u1, u2) + getdist(u1, t[2][0]) - getdist(u2, t[2][0])) / 2; E[2] = exact_size(u1, s, t[2]); }
	}
	
	bool flag = false;
	if (E[1] >= 1 && max({E[0], E[1], (int)t[2].size() + E[3]}) <= N / 2) flag = true;
	if (E[2] >= 1 && max({E[0] + (int)t[1].size(), E[2], E[3]}) <= N / 2) flag = true;
	if (flag == true) return (diameter + minx) / 2;
	return -1 * ((diameter + minx) / 2);
}

Compilation message

towns.cpp: In function 'int exact_size(int, int, std::vector<int>)':
towns.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (t[1].size() > N / 2) { int s = (getdist(u1, u2) + getdist(u1, t[1][0]) - getdist(u2, t[1][0])) / 2; E[1] = exact_size(u1, s, t[1]); }
       ~~~~~~~~~~~~^~~~~~~
towns.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (t[2].size() > N / 2) { int s = (getdist(u1, u2) + getdist(u1, t[2][0]) - getdist(u2, t[2][0])) / 2; E[2] = exact_size(u1, s, t[2]); }
       ~~~~~~~~~~~~^~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 384 KB Output is correct
2 Correct 14 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 18 ms 512 KB Output is correct
5 Correct 19 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 512 KB Output is correct
2 Correct 14 ms 512 KB Output is correct
3 Correct 18 ms 512 KB Output is correct
4 Correct 18 ms 512 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 384 KB Output is correct
2 Correct 18 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 18 ms 512 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 384 KB Output is correct
2 Correct 19 ms 1048 KB Output is correct
3 Correct 20 ms 1024 KB Output is correct

Subtask #6
0 / 39.0

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