oj.uz

Submission #233357

# Submission time Handle Problem Language Result Execution time Memory
233357 2020-05-20T10:17:36 Z mieszko11b Towns (IOI15_towns) C++14
100 / 100
 30 ms 432 KB 
#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

int v = 0, s, t, r;
int distv[120], dists[120];

bool sameConn(int x1, int x2) {
	int x = getDistance(x1, x2);
	return (dists[x1] + dists[x2] - x > 2 * r);
}

int hubDistance(int N, int sub) {
	int maxv = 0;
	for(int i = 0 ; i < N ; i++) {
		distv[i] = getDistance(v, i);
		maxv = max(maxv, distv[i]);
	}
	
	for(int i = 0 ; i < N ; i++)
		if(distv[i] == maxv)
			s = i;
			
	int dsv = maxv;
			
	maxv = 0;
	for(int i = 0 ; i < N ; i++) {
		dists[i] = getDistance(s, i);
		maxv = max(maxv, dists[i]);
	}
	
	int d = maxv;
	
	for(int i = 0 ; i < N ; i++)
		if(dists[i] == maxv)
			t = i;	

	int res = 1e9;
	vector<int> poss;
	for(int i = 0 ; i < N ; i++) {
		int a = (dists[i] + dsv - distv[i]) / 2;
		int b = dsv - a;
		if(max({a, b, d - a}) < res) {
			res = max({a, b, d - a});
			poss.clear();
			poss.push_back(a);
		} else if(max({a, b, d - a}) == res)
			poss.push_back(a);
		//~ cout << i << " " << res << endl;
	}
	
	vector<int> B;
	for(int i = 0 ; i < N ; i++)
		B.push_back((dists[i] + dsv - distv[i]) / 2);
		
	sort(B.begin(), B.end());
	
	int m;
	if(B.size() % 2 == 0) {
		int m1 = B[B.size() / 2 - 1];
		int m2 = B[B.size() / 2];
		if(m1 == m2)
			m = m1;
		else {
			if(find(poss.begin(), poss.end(), m1) == poss.end()
				&& find(poss.begin(), poss.end(), m2) == poss.end()) {
				//~ cout << "aa" << endl;
				return -res;
			}		
			return res;
		}
	} else
		m = B[B.size() / 2];
		
	if(find(poss.begin(), poss.end(), m) == poss.end()) {
		//~ cout << "aa" << endl;
		return -res;
	}
	r = m;
		
	vector<int> list, bucket;
	for(int i = 0 ; i < N ; i++) {
		if((dists[i] + dsv - distv[i]) / 2 == m) {
			if(list.empty() || !sameConn(i, list.back())) {
				list.push_back(i);
				if(!bucket.empty()) {
					list.push_back(bucket.back());
					bucket.pop_back();
				}
			} else
				bucket.push_back(i);
		}
	}
		
	int T = list.back();
		
	int cnt = 0;
	while(!list.empty()) {
		if(sameConn(list.back(), T)) {
			cnt++;
			if(list.size() > 1) {
				list.pop_back();
				list.pop_back();
			} else {
				bucket.push_back(list.back());
				list.pop_back();
			}
		} else {
			list.pop_back();
			if(bucket.empty()) {
				//~ cout << "D" << endl;
				return res;
			}
			bucket.pop_back();
			cnt++;
		}
	}
	
	cnt += bucket.size();
	
	if(cnt <= N / 2) {
		//~ cout << "c" << endl;
		return res;
	}
	//~ cout << "ab" << endl;
	return -res;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:125:21: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  cnt += bucket.size();
                     ^
towns.cpp:19: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 24 ms 384 KB Output is correct
2 Correct 23 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 25 ms 384 KB Output is correct
5 Correct 29 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 384 KB Output is correct
2 Correct 22 ms 384 KB Output is correct
3 Correct 30 ms 384 KB Output is correct
4 Correct 25 ms 384 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 384 KB Output is correct
2 Correct 27 ms 432 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 25 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 384 KB Output is correct
2 Correct 27 ms 384 KB Output is correct
3 Correct 26 ms 384 KB Output is correct

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 384 KB Output is correct
2 Correct 28 ms 384 KB Output is correct
3 Correct 25 ms 384 KB Output is correct