oj.uz

Submission #790280

# Submission time Handle Problem Language Result Execution time Memory
790280 2023-07-22T14:07:25 Z NothingXD Towns (IOI15_towns) C++17
100 / 100
 16 ms 356 KB 
#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << " ";
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 200 + 10;

int n, r1, r2, dis[2][maxn];

int getlca(int v){
	return (dis[0][v] + dis[0][r1] - dis[1][v]) / 2;
}

bool iseq(int x, int y, int cent){
	bool tmp = (getDistance(x, y) < (dis[0][x] + dis[0][y] - 2 * cent));
	//debug(x, y, cent, tmp);
	return tmp;
}

bool findmajor(vector<int> v, int cent){
	//debug(1);
	int N = v.size();
	vector<pii> a;
	vector<int> b;
	for (int i = 1; i < N; i += 2){
		if (iseq(v[i-1], v[i], cent)){
			a.push_back({v[i-1], 2});
		}
		else{
			b.push_back(v[i-1]);
			b.push_back(v[i]);
		}
	}
	if (N & 1){
		a.push_back({v.back(), 1});
	}
	if (a.empty()) return false;
	int cnt = 0, idx = 0;
	for (int i = 0; i < a.size(); i++){
		if (cnt == 0){
			idx = i;
			cnt = a[i].S;
			continue;
		}
		bool tmp = iseq(a[idx].F, a[i].F, cent);
		if (tmp) cnt += a[i].S;
		else cnt -= a[i].S;
		if (cnt < 0){
			cnt = abs(cnt);
			idx = i;
		}
	}
	cnt = a[idx].S;
	for (int i = 0; i < a.size(); i++){
		if (i == idx) continue;
		bool tmp = iseq(a[idx].F, a[i].F, cent);
		if (tmp) cnt += a[i].S;
	}
	for (auto x: b){
		bool tmp = iseq(a[idx].F, x, cent);
		if (tmp) cnt++;
	}
	return (cnt > n/2);
}

int hubDistance(int N, int sub) {
	memset(dis, 0, sizeof dis);
	n = N;
	for (int i = 1; i < n; i++){
		dis[0][i] = getDistance(0, i);
	}
	r1 = max_element(dis[0], dis[0] + n) - dis[0];
	dis[1][0] = dis[0][r1];
	for (int i = 1; i < n; i++){
		if (i == r1) continue;
		dis[1][i] = getDistance(r1, i);
	}
	r2 = max_element(dis[1], dis[1] + n) - dis[1];
	//debug(r1, r2);
	int lca = getlca(r2);
	int ans = dis[1][r2];
	vector<int> cent = {dis[0][r1]};
	for (int i = 0; i < n; i++){
		int tmp = getlca(i);
		if (tmp < lca) continue;
		int res = max(dis[0][r1] - tmp, dis[1][r2] - dis[0][r1] + tmp);
		if (res < ans){
			cent.clear();
			ans = res;
		}
		if (res == ans){
			cent.push_back(tmp);
		}
	}
	sort(all(cent));
	cent.resize(distance(cent.begin(), unique(all(cent))));
	ans = -ans;
	for (auto x: cent){
		int up = 0, down = 0;
		vector<int> mid;
		for (int i = 0; i < n; i++){
			int tmp = getlca(i);
			if (tmp < x) up++;
			else if (tmp > x) down++;
			else mid.push_back(i);
		}
		//debug(x, up, down, mid.size());
		if (up > n/2 || down > n/2) continue;
		if (mid.size() <= n/2){
			ans = abs(ans);
			continue;
		}
		if (!findmajor(mid, x)) ans = abs(ans);
	}

	return ans;
}

Compilation message

towns.cpp: In function 'bool findmajor(std::vector<int>, int)':
towns.cpp:43:16: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   43 |  int N = v.size();
      |          ~~~~~~^~
towns.cpp:60: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]
   60 |  for (int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
towns.cpp:75: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]
   75 |  for (int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:93:39: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   93 |  r1 = max_element(dis[0], dis[0] + n) - dis[0];
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
towns.cpp:99:39: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   99 |  r2 = max_element(dis[1], dis[1] + n) - dis[1];
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
towns.cpp:130:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  130 |   if (mid.size() <= n/2){
      |       ~~~~~~~~~~~^~~~~~
towns.cpp:87:28: warning: unused parameter 'sub' [-Wunused-parameter]
   87 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 352 KB Output is correct
2 Correct 9 ms 348 KB Output is correct
3 Correct 12 ms 340 KB Output is correct
4 Correct 16 ms 352 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 12 ms 352 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 12 ms 356 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 12 ms 356 KB Output is correct
3 Correct 12 ms 340 KB Output is correct

Subtask #6
39.0 / 39.0

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