oj.uz

Submission #289597

# Submission time Handle Problem Language Result Execution time Memory
289597 2020-09-02T18:51:03 Z amoo_safar Towns (IOI15_towns) C++17
100 / 100
 22 ms 896 KB 
#include "towns.h"

#include <bits/stdc++.h>

using namespace std;


const int N = 200;
int d0[N], d1[N], D[N], val[N], disth[N];
int par[N], sz[N];
int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
bool flg = false;
void Unite(int u, int v){
	if(flg) return ;
	u = Find(u);
	v = Find(v);
	if(u == v) return ;
	par[u] = v;
	sz[v] += sz[u];
	return ;
}

typedef pair<int, int> pii;

bool Same(int u, int v){
	if(Find(u) == Find(v)) return true;
	if(disth[u] + disth[v] == getDistance(u, v)) return false; 
	Unite(u, v);
	return true;
}

int hubDistance(int n, int sub) {
	iota(par, par + N, 0);
	fill(sz, sz + N, 1);
	flg = false;
	//Unite(0, 1);
	//cerr << "! " << sz[Find(1)] << '\n';
	assert(sub >= 0);
	d0[0] = 0;
	for(int i = 1; i < n; i++)
		d0[i] = getDistance(0, i);
	int mx = max_element(d0, d0 + n) - d0;

	d1[0] = d0[mx];
	for(int i = 1; i < n; i++)
		d1[i] = (i == mx ? 0 : getDistance(i, mx));

	int dia = *max_element(d1, d1 + n);
	int R = 2000000;

	for(int i = 0; i < n; i++){
		int X = (d0[i] + d1[i] - d0[mx]) / 2;
		int P = d1[i] - X;
		R = min(R, max(P, dia - P));
		D[i] = X;
		val[i] = P;
	}
	if(sub <= 2) return R;
	//map<int, vector<int> > mp;
	
	vector<int> Hub, VH, VD;
	for(int i = 0; i < n; i++){
		if(R == max(val[i], dia - val[i])){
			Hub.push_back(val[i]);
		}
		VD.push_back(val[i]);
	}
	sort(Hub.begin(), Hub.end());
	Hub.resize(unique(Hub.begin(), Hub.end()) - Hub.begin());
	
	sort(VD.begin(), VD.end());
	assert(Hub.size() <= 2);

	for(auto x : Hub){
		int ls = lower_bound(VD.begin(), VD.end(), x) - VD.begin();
		int bg = n - (upper_bound(VD.begin(), VD.end(), x) - VD.begin());
		int mxx = max(ls, bg);
		
		if(sub == 4){
			int rrr = max({ls, bg, n - ls - bg});
			if(rrr + rrr <= n) return R;
		}
		if(mxx + mxx < n) VH.push_back(x);
		if(mxx + mxx == n) return R;
		
	}
	if(sub == 4) return -R;
	if(VH.empty()) return -R;
	assert(VH.size() == 1);

	int hb = VH[0];
	for(int i = 0; i < n; i++) disth[i] = abs(hb - val[i]) + D[i];
	
	int la = 0, hp = 1;

	for(int i = 1; i < n; i++){
		if(hp == 0){
			la = i;
			hp = 1;
			continue;
		}
		if(Same(i, la)) hp ++;
		else hp --;
	}
	if(hp == 0) return R;

	int maj = la;
	int sam = 0;
	int all = 0;
	flg = true;
	for(int i = 0; i < n; i++){
		if(par[i] != i) continue;
		all += sz[i];
		if(Same(maj, i)) sam += sz[i];
		//if(Same(maj, i)) sam ++;
	}
	assert(all == n);
	if(maj == -1) return R;
	if(sam + sam > n) return -R;
	return R;
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:45:35: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   45 |  int mx = max_element(d0, d0 + n) - d0;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:78:49: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   78 |   int ls = lower_bound(VD.begin(), VD.end(), x) - VD.begin();
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:79:14: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   79 |   int bg = n - (upper_bound(VD.begin(), VD.end(), x) - VD.begin());
      |            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 384 KB Output is correct
2 Correct 16 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 21 ms 384 KB Output is correct
5 Correct 21 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

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

Subtask #6
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 512 KB Output is correct
2 Correct 22 ms 896 KB Output is correct
3 Correct 22 ms 896 KB Output is correct