제출 #433353

#제출 시각아이디문제언어결과실행 시간메모리
433353timmyfeng도시들 (IOI15_towns)C++17
100 / 100
22 ms880 KiB
#include <bits/stdc++.h> using namespace std; #include "towns.h" const int N = 110; int dist_0[N], dist_u[N], pos[N], color[N]; int hubDistance(int n, int subtask) { for (int i = 1; i < n; ++i) { dist_0[i] = getDistance(0, i); } int u = max_element(dist_0, dist_0 + n) - dist_0; dist_u[0] = dist_0[u]; for (int i = 1; i < n; ++i) { dist_u[i] = u == i ? 0 : getDistance(u, i); } int v = max_element(dist_u, dist_u + n) - dist_u; pos[0] = (dist_0[u] - dist_0[v] + dist_u[v]) / 2; for (int i = 1; i < n; ++i) { pos[i] = min(pos[0], (dist_0[u] - dist_0[i] + dist_u[i]) / 2); } int ans = INT_MAX; map<int, vector<int>> groups; for (int i = 0; i < n; ++i) { ans = min(ans, max(pos[i], dist_u[v] - pos[i])); groups[pos[i]].push_back(i); } int left = 0, right = n; for (auto &[len, nodes] : groups) { right -= nodes.size(); if (max(len, dist_u[v] - len) == ans) { if (max(left, right) <= n / 2) { int j = -1, balance = 0; for (auto i : nodes) { if (balance == 0) { j = i; } if (i == j || getDistance(i, j) < dist_u[i] + dist_u[j] - 2 * len) { color[i] = j, ++balance; } else { color[i] = i, --balance; } } int k = -1, count = 0; for (auto i : nodes) { if (color[i] == i && getDistance(i, j) < dist_u[i] + dist_u[j] - 2 * len) { k = i; } count += color[i] == k; } return count <= n / 2 ? ans : -ans; } } left += nodes.size(); } return -ans; }

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:15:45: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   15 |     int u = max_element(dist_0, dist_0 + n) - dist_0;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
towns.cpp:21:45: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   21 |     int v = max_element(dist_u, dist_u + n) - dist_u;
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
towns.cpp:36:29: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   36 |         right -= nodes.size();
      |                             ^
towns.cpp:63:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   63 |         left += nodes.size();
      |                            ^
towns.cpp:10:28: warning: unused parameter 'subtask' [-Wunused-parameter]
   10 | int hubDistance(int n, int subtask) {
      |                        ~~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...