oj.uz

Submission #798615

# Submission time Handle Problem Language Result Execution time Memory
798615 2023-07-30T21:48:48 Z Username4132 Towns (IOI15_towns) C++14
100 / 100
 14 ms 1068 KB 
#include "towns.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

const int MAXN = 120;
int n, dis, mx, v=-1, w=-1, d1[MAXN], d2[MAXN], hdi[MAXN];

inline int calc(int ver){
	return (mx+d2[ver]-d1[ver])>>1;
}

inline bool check(int i, int j){
	return getDistance(i, j) < hdi[i] + hdi[j];
}

pii solve(vector<int>& vec, int l){
	if(l==(int)vec.size()) return {-1, -1};
	vector<int> eq, di;
	eq.PB(vec[l]);
	int cur=l+1;
	while(cur<(int)vec.size() && eq.size()!=di.size()){
		if(check(vec[l], vec[cur])) eq.PB(vec[cur]);
		else di.PB(vec[cur]);
		++cur;
	}
	if(eq.size()!=di.size()) return {vec[l], eq.size()};
	pii val = solve(vec, cur);
	if(val.F==-1) return {-1, -1};
	if(check(vec[l], val.F)) return {vec[l], val.S + eq.size()};
	int cou=val.S;
	for(int el:di) cou+=check(el, val.F);
	if(2*cou>((int)vec.size())-l) return {val.F, cou};
	else return {-1, -1};
}

bool test(int d){
	int x=0, y=0;
	vector<int> us;
	forn(i, n){
		int nd = calc(i);
		if(nd>d) ++x;
		else if(nd<d) ++y;
		else us.PB(i);
	}
	if(x>(n/2) || y>(n/2)) return false;
	for(int el:us) hdi[el]=d2[el]-calc(el);
	pii ret = solve(us, 0);
	return ret.S<=(n/2);
}

int hubDistance(int N, int sub) {
	n=N;
	forn(i, n) d1[i]=d2[i]=0;
	mx=-1;
	forsn(i, 1, n){
		d1[i]=getDistance(0, i);
		if(mx<d1[i]) mx=d1[i], v=i;
	}
	dis=-1;
	forn(i, n) if(i!=v){
		d2[i]=getDistance(v, i);
		if(dis<d2[i]) dis=d2[i], w=i;
	}

	int cc = calc(w);
	int ans = 1000000000;
	forn(i, n){
		int d = calc(i);
		if(d<=cc) ans = min(ans, max(d, dis-d));
	}

	vector<int> used;
	bool yes=false;
	forn(i, n){
		int d = calc(i);
		if(max(d, dis-d)==ans && find(used.begin(), used.end(), d)==used.end()) yes|=test(d), used.PB(d);
	}

	return (yes? ans : -ans);
}

Compilation message

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:59:28: warning: unused parameter 'sub' [-Wunused-parameter]
   59 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 724 KB Output is correct
2 Correct 9 ms 800 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 12 ms 852 KB Output is correct
5 Correct 12 ms 840 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 892 KB Output is correct
2 Correct 9 ms 700 KB Output is correct
3 Correct 12 ms 828 KB Output is correct
4 Correct 12 ms 852 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 596 KB Output is correct
2 Correct 14 ms 840 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 12 ms 828 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 836 KB Output is correct
2 Correct 12 ms 824 KB Output is correct
3 Correct 12 ms 888 KB Output is correct

Subtask #6
39.0 / 39.0

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