제출 #1258268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258268		kl0989e	도시들 (IOI15_towns)	C++20	26 / 100	305 ms	1248 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()

const int maxn=110;

vector<vi> dist(4*maxn,vi(4*maxn));

int hubDistance(int n, int sub) {
	for (int i=0; i<n; i++) {
		dist[i][i]=0;
		for (int j=i+1; j<n; j++) {
			dist[i][j]=getDistance(i,j);
			dist[j][i]=dist[i][j];
		}
	}
	int ans=2e9;
	for (int i=0; i<n; i++) {
		for (int j=i+1; j<n; j++) {
			map<int,int> dst;
			for (int k=0; k<n; k++) {
				if (k==i || k==j) {
					continue;
				}
				dst[(dist[i][k]+dist[i][j]-dist[j][k])/2]=max(dst[(dist[i][k]+dist[i][j]-dist[j][k])/2],(dist[i][k]+dist[j][k]-dist[i][j])/2);
			}
			int val=0;
			int prv=0;
			map<int,int> nw;
			for (auto pt=dst.begin(); pt!=dst.end(); pt++) {
				val+=pt->fi-prv;
				prv=pt->fi;
				nw[pt->fi]=max(pt->se,val);
				val=nw[pt->fi];
			}
			prv=dist[i][j];
			val=0;
			auto pt=dst.end();
			do {
				pt--;
				val+=prv-pt->fi;
				prv=pt->fi;
				val=max(val,pt->se);
				pt->se=max(val,nw[pt->fi]);
				ans=min(ans,pt->se);
			} while (pt!=dst.begin());
		}
	}
	bool has=0;
	for (int i=0; i<n && !has; i++) {
		for (int j=i+1; j<n && !has; j++) {
			map<int,int> dst;
			map<int,vi> adj;
			for (int k=0; k<n; k++) {
				if (k==i || k==j) {
					continue;
				}
				dst[(dist[i][k]+dist[i][j]-dist[j][k])/2]=max(dst[(dist[i][k]+dist[i][j]-dist[j][k])/2],(dist[i][k]+dist[j][k]-dist[i][j])/2);
				adj[(dist[i][k]+dist[i][j]-dist[j][k])/2].pb(k);
			}
			int val=0;
			int prv=0;
			int sum=1;
			map<int,int> nw;
			map<int,int> cnts;
			for (auto pt=dst.begin(); pt!=dst.end(); pt++) {
				val+=pt->fi-prv;
				prv=pt->fi;
				nw[pt->fi]=max(pt->se,val);
				val=nw[pt->fi];
				cnts[pt->fi]=sum;
				sum+=adj[pt->fi].size();
			}
			sum=1;
			prv=dist[i][j];
			val=0;
			auto pt=dst.end();
			do {
				pt--;
				val+=prv-pt->fi;
				prv=pt->fi;
				val=max(val,pt->se);
				pt->se=max(val,nw[pt->fi]);
				cnts[pt->fi]=max(sum,cnts[pt->fi]);
				sum+=adj[pt->fi].size();
				if (ans==pt->se) {
					bool ok=1;
					ok&=(cnts[pt->fi]<=n/2);
					for (auto l:adj[pt->fi]) {
						int tcnt=0;
						for (auto m:adj[pt->fi]) {
							if (dist[l][m]!=(dist[i][l]+dist[j][l]-dist[i][j])/2+(dist[i][m]+dist[j][m]-dist[i][j])/2) {
								tcnt++;
							}
						}
						ok&=tcnt<=n/2;
					}
					has|=ok;
				}
			} while (pt!=dst.begin());
		}
	}
	return (has?ans:-ans);
}

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