제출 #383888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383888		LucaDantas	도시들 (IOI15_towns)	C++17	48 / 100	22 ms	1260 KiB

towns

#include "towns.h"
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <vector>
#include <map>
 
constexpr int maxn = 300;
 
int dp[maxn][maxn], c[maxn];

std::map<int, std::vector<int>> filhos;
 
int get(int i, int j) {
	if(i > j) std::swap(i, j);
	return dp[i][j] != -1 ? dp[i][j] : dp[i][j] = getDistance(i, j);
}

struct DSU
{
	int pai[maxn], peso[maxn];
	void init() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
	int find(int x) { return pai[x] == x?x:pai[x]=find(pai[x]); }
	void join(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return;
		if(peso[a] < peso[b])
			std::swap(a, b);
		pai[b] = a;
		peso[a] += peso[b];
	}
	int sz(int x) { return peso[find(x)]; }
} dsu;

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }
 
int hubDistance(int N, int sub) {
	memset(dp, -1, sizeof dp);
	memset(c, 0, sizeof c);
	filhos.clear();
	dsu.init();
	int a = 0, b = 0, dist = 0;
	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < N; j++) {
			if(a != j) {
				int v = get(a, j);
				if(v > dist) b = j, dist = v;
			}
		}
		if(!i) std::swap(a, b);
	// 	if(!i) a = b, dist = 0, b = 0;
	}
	b = 0;
	// printf("%d %d %d\n", a, b, dist);
	int R = 0x3f3f3f3f;
	for(int i = 0; i < N; i++) {
		if(i == a || i == b) continue;
		int d1 = get(a, i), d2 = get(b, i);
		c[i] = (d1 + d2 - get(a, b)) >> 1;
		// printf("%d %d %d %d\n", i, d1, d2, c[i]);
		// printf("%d (%d %d) (%d %d) %d\n", i, d1, dist-d1, d1-c[i], dist - (d1-c[i]), c[i]);
		R = min(R, max(d1 - c[i], dist - d1 + c[i]));
		filhos[d1-c[i]].push_back(i);
	}

	if(sub <= 2) return R;
	if(sub == 4) {
		int sz = 1;
		bool ok = 0;
		for(auto it : filhos) {
			if(it.first == R || it.first == dist - R) {
				if(sz <= (N >> 1) && N - sz - it.second.size() <= (N >> 1)
				&& it.second.size() <= (N >> 1)) ok = 1;
			}
			sz += it.second.size();
		}
		return R * (ok?1:-1);
	}
	int sz = 1;
	bool ok = 0;
	for(auto it : filhos) {
		if(it.first != R && it.first != dist - R) {
			sz += (int)(it.second).size();
			continue;
		}
		if(sz <= (N >> 1) && N - sz - (int)(it.second).size() <= (N >> 1)) ok = 1;
		std::vector<int> v = (it.second);
		int n = (int)v.size();
		for(int i = 0; i < n; i++)
			for(int j = i+1; j < n; j++)
				if(get(v[i], v[j]) != c[v[i]] + c[v[j]])
					dsu.join(v[i], v[j]);
		for(int i = 0; i < n; i++)
			ok &= dsu.sz(v[i]) <= (N >> 1);
		if(ok) return R;
		sz += n;
	}
	return R * (ok?1:-1);
}

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:74:52: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |     if(sz <= (N >> 1) && N - sz - it.second.size() <= (N >> 1)
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
towns.cpp:75:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |     && it.second.size() <= (N >> 1)) ok = 1;
      |        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
towns.cpp:77:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   77 |    sz += it.second.size();
      |                         ^

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