Submission #868047

#	Time	Username	Problem	Language	Result	Execution time	Memory
868047		waldi	Towns (IOI15_towns)	C++17	35 / 100	15 ms	1116 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define fi first
#define se second
#define debug(a) cerr << #a << ": " << a << "\n";
using namespace std;
typedef pair<int, int> pii;

int hubDistance(int n, int sub){
	int a = 0;
	vector<int> od0(n, 0);
	FOR(i, 1, n-1){
		od0[i] = getDistance(0, i);
		if(od0[i] > od0[a]) a = i;
	}
	
	int b = 0;
	vector<int> oda(n, 0);
	REP(i, n) if(i != a){
		oda[i] = getDistance(a, i);
		if(oda[i] > oda[b]) b = i;
	}
	int sred = oda[b];
	
	vector<int> odb(n, 0);
	REP(i, n) if(i != b) odb[i] = getDistance(b, i);
	
	set<int> secik;
	REP(i, n){
		int t = (oda[i]+odb[i]-sred)>>1, odla = oda[i]-t;
		secik.emplace(odla);
	}
	
	int wyn = sred+1, poz = -1;
	for(int off : secik){
		int maks = 0;
		REP(i, n){
			int t = (oda[i]+odb[i]-sred)>>1, odla = oda[i]-t;
			maks = max(maks, t + abs(off-odla));
		}
		if(maks < wyn) wyn = maks, poz = off;
	}
	
	if(sub <= 2) return wyn;
	
	if(sub == 4){
		int lewo = 0, prawo = 0, ja = 0;
		REP(i, n){
			int t = (oda[i]+odb[i]-sred)>>1;
			int odla = oda[i]-t;
			if(odla < poz) ++lewo;
			if(odla == poz) ++ja;
			if(odla > poz) ++prawo;
		}
		bool zle = 0;
		zle |= lewo > n/2;
		zle |= prawo > n/2;
		zle |= ja > n/2;// wiem to jest jedno poddrzewo
		if(zle) wyn = -wyn;
		return wyn;
	}
	
	return wyn;
}

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39