제출 #1218989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218989		Zbyszek99	Towns (IOI15_towns)	C++20	100 / 100	11 ms	328 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

map<pii,int> query_map;

int ask(int a, int b)
{
	if(query_map.find({a,b}) != query_map.end()) return query_map[{a,b}];
	int d = getDistance(a,b);
	query_map[{a,b}] = d;
	query_map[{b,a}] = d;
	return d;
}

int dist1[110];
int dist2[110];
int dist3[110];
int V[110];

int hubDistance(int n, int sub) 
{
	query_map = {};
	rep(i,n)
	{
		dist1[i] = 0;
		dist2[i] = 0;
		dist3[i] = 0;
	}
	rep2(i,1,n-1) dist1[i] = ask(0,i);
	dist1[0] = 0;
	int u = 0;
	rep2(i,1,n-1)
	{
		if(dist1[i] > dist1[u]) u = i;
	}
	rep(i,n) if(i != u) dist2[i] = ask(u,i);
	int max_dist = 0;
	rep(i,n) max_dist = max(max_dist,dist2[i]);
	rep(i,n) dist3[i] = (dist1[i] + dist2[i] - dist1[u])/2;
	int R;
	vi dists_u;
	rep(i,n) dists_u.pb(dist2[i] - dist3[i]);
	sort(all(dists_u));
	int pop = 0;
	vi hubs;
	forall(it,dists_u)
	{
		if(it >= (max_dist+2)/2)
		{
			hubs.pb(pop);
			hubs.pb(it);
			break;
		}
		pop = it;
	}
	R = min(max(hubs[0],max_dist-hubs[0]),max(hubs[1],max_dist-hubs[1]));
	int cnt0 = 0;
	int cnt1 = 0;
	rep(i,n)
	{
		if((dist2[i]-dist3[i]) <= hubs[0]) cnt0++;
		else cnt1++;
	}
	int H = hubs[0];
	if((cnt0 < cnt1 && max(hubs[1],max_dist-hubs[1]) == R) || max(hubs[0],max_dist-hubs[0]) != R) H = hubs[1];
	vi bucket;
	vi list;
	rep(i,n)
	{
		V[i] = dist2[i] - dist3[i];
	}
	rep(i,n)
	{
		if(siz(list) == 0)
		{
			list.pb(i);
		}
		else
		{
			if((dist2[i] + dist2[list.back()] - 2*H != ask(i,list.back()) && V[i] == V[list.back()]) || (V[i] < H && V[list.back()] < H) || (V[i] > H && V[list.back()] > H))
			{
				bucket.pb(i);
			}
			else
			{
				list.pb(i);
				if(siz(bucket) != 0)
				{
					list.pb(bucket.back());
					bucket.pop_back();
				}
			}
		}
	}
	int T = list.back();
	list.pop_back();
	bucket.pb(T);
	while(!list.empty())
	{
		int T2 = list.back();
		if((ask(T2,T) != dist2[T2] + dist2[T] - 2*H && V[T] == V[T2]) || (V[T] < H && V[T2] < H) || (V[T] > H && V[T2] > H))
		{
			if(siz(list) >= 2)
			{
				list.pop_back();
				list.pop_back();
			}
			else
			{
				bucket.pb(list.back());
				list.pop_back();
			}
		}
		else
		{
			if(siz(bucket) == 0)
			{
				return R;
			}
			bucket.pop_back();
			list.pop_back();
		}
	}
	if(siz(bucket) > 0) return -R;
	return R;
}

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