제출 #1065178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1065178		pawned	Towns (IOI15_towns)	C++17	13 / 100	11 ms	1112 KiB

towns

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "towns.h"

int hubDistance(int N, int sub) {
	vector<vi> getDist(N, vi(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			getDist[i][j] = getDistance(i, j);
			getDist[j][i] = getDist[i][j];
		}
	}
	int a = -1;
	int maxd = -1;
	for (int i = 0; i < N; i++) {
		int cdist = getDist[0][i];
		if (cdist > maxd) {
			a = i;
			maxd = cdist;
		}
	}
	int b = -1;
	maxd = -1;
	vi dist1(N, -1);
	for (int i = 0; i < N; i++) {
		dist1[i] = getDist[a][i];
		if (dist1[i] > maxd) {
			b = i;
			maxd = dist1[i];
		}
	}
	vi dist2(N, -1);
	for (int i = 0; i < N; i++) {
		dist2[i] = getDist[b][i];
	}
	int dia = dist1[b];
//	cout<<"a, b, dia: "<<a<<", "<<b<<"; "<<dia<<endl;
	int ans = 1e9;
	for (int i = 0; i < N; i++) {
		int s = (dia + abs(dist1[i] - dist2[i])) / 2;
		ans = min(ans, s);
	}
	vi cen;
	map<int, int> cnts;
	for (int i = 0; i < N; i++) {
		cnts[dist1[i] - dist2[i]]++;
	}
/*	cout<<"cnts: "<<endl;
	for (ii p : cnts)
		cout<<p.fi<<": "<<p.se<<endl;*/
	int ctr = 0;
	for (ii p : cnts) {
		if (((dia + abs(p.fi)) / 2 == ans) && (p.se <= N / 2) && (ctr <= N / 2) && (N - p.se - ctr <= N / 2)) {
			// possibly works
			int cdist = (dia + p.fi) / 2;	// distance from c to a
			vi ins;	// all the leaf nodes w/ this 
			for (int i = 0; i < N; i++) {
				if (dist1[i] - dist2[i] == p.fi)
					ins.pb(i);
			}
			map<int, int> distc;
			for (int x : ins) {
				distc[x] = getDist[x][a] - cdist;
			}
			bool works = true;
			for (int x : ins) {
				int cnt = 0;
				for (int y : ins) {
					if (getDist[x][y] == distc[x] + distc[y])
						cnt++;
				}
				if (cnt > N / 2)
					works = false;
			}
			if (works)
				return ans;
		}
		ctr += p.se;
	}
	return -ans;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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