| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1015388 |
2024-07-06T09:59:38 Z |
우민규(#10889) |
Towns (IOI15_towns) |
C++14 |
|
13 ms |
528 KB |
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> qans;
int get_distance(int i, int j) {
if (i > j) swap(i, j);
if (qans[i][j] != -1) return qans[i][j];
return qans[i][j] = getDistance(i, j);
}
int hubDistance(int n, int sub) {
qans.assign(n, vector<int>(n, -1));
for (int i = 0; i < n; ++i) qans[i][i] = 0;
// get diameter of tree
int u = 1;
int uv = get_distance(0, u);
for (int i = 2; i < n; ++i) {
int di = get_distance(0, i);
if (di > uv) {
u = i;
uv = di;
}
}
int v = 0;
for (int i = 0; i < n; ++i) {
int di = get_distance(u, i);
if (di > uv) {
v = i;
uv = di;
}
}
// u - v w. length dd is diameter
unordered_map<int, vector<int>> by_uh;
int u0 = get_distance(u, 0);
int v0 = get_distance(v, 0);
int ux = (u0 + uv - v0) / 2;
int r = INT_MAX;
for (int i = 0; i < n; ++i) {
int iu = get_distance(i, u);
int i0 = get_distance(i, 0);
// 2*(i-h)
int ih = (iu + i0 - u0) / 2;
int uh = iu - ih;
by_uh[uh].push_back(i);
if (uh > ux) continue;
r = min(r, max(uh, uv - uh));
}
// true -> in same subtree
// false -> in diff.
auto is_same_subtree = [&](int a, int b, int req_uh) -> bool {
int ab = get_distance(a, b);
int ua = get_distance(u, a);
int ub = get_distance(u, b);
int uh = (ua + ub - ab) / 2;
return uh != req_uh;
};
// true -> balanced
// false -> not
auto determine_child = [&](int uh) -> bool {
// return false;
vector<int> rc = by_uh[uh];
vector<pair<int, int>> mounds;
vector<int> diff_from_mound;
int count = 0;
for (auto v : rc) {
if (count == 0) {
mounds.push_back({v, 1});
count = 1;
} else {
if (is_same_subtree(mounds.back().first, v, uh)) {
mounds.back().second += 1;
count += 1;
} else {
diff_from_mound.push_back(v);
count -= 1;
}
}
}
if (count == 0) return false;
int majority_node = mounds.back().first;
int majority_subtree_size = 0;
for (auto [rep, count] : mounds) {
if (is_same_subtree(rep, majority_node, uh)) {
majority_subtree_size += count;
}
}
for (auto v : diff_from_mound) {
if (is_same_subtree(majority_node, v, uh)) {
majority_subtree_size += 1;
}
}
return majority_subtree_size <= n / 2;
};
if (by_uh.count(r)) {
int cu = 0, cr = 0, cv = 0;
for (auto& [k, v] : by_uh) {
if (k < r) cu += v.size();
if (k == r) cr += v.size();
if (k > r) cv += v.size();
}
if (cu <= n / 2 && cv <= n / 2) {
if (cr <= n / 2) return r;
if (determine_child(r)) return r;
}
}
if (r != uv - r && by_uh.count(uv - r)) {
int cu = 0, cr = 0, cv = 0;
for (auto& [k, v] : by_uh) {
if (k < uv - r) cu += v.size();
if (k == uv - r) cr += v.size();
if (k > uv - r) cv += v.size();
}
if (cu <= n / 2 && cv <= n / 2) {
if (cr <= n / 2) return r;
if (determine_child(uv - r)) return r;
}
}
return -r;
}
#ifndef EVAL
#include "grader.cpp"
#endif
Compilation message
towns.cpp: In lambda function:
towns.cpp:72:15: warning: declaration of 'v' shadows a previous local [-Wshadow]
72 | for (auto v : rc) {
| ^
towns.cpp:28:7: note: shadowed declaration is here
28 | int v = 0;
| ^
towns.cpp:89:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
89 | for (auto [rep, count] : mounds) {
| ^
towns.cpp:89:21: warning: declaration of 'count' shadows a previous local [-Wshadow]
89 | for (auto [rep, count] : mounds) {
| ^~~~~
towns.cpp:71:9: note: shadowed declaration is here
71 | int count = 0;
| ^~~~~
towns.cpp:94:15: warning: declaration of 'v' shadows a previous local [-Wshadow]
94 | for (auto v : diff_from_mound) {
| ^
towns.cpp:28:7: note: shadowed declaration is here
28 | int v = 0;
| ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:104:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
104 | for (auto& [k, v] : by_uh) {
| ^
towns.cpp:104:20: warning: declaration of 'v' shadows a previous local [-Wshadow]
104 | for (auto& [k, v] : by_uh) {
| ^
towns.cpp:28:7: note: shadowed declaration is here
28 | int v = 0;
| ^
towns.cpp:105:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
105 | if (k < r) cu += v.size();
| ^
towns.cpp:106:32: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
106 | if (k == r) cr += v.size();
| ^
towns.cpp:107:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
107 | if (k > r) cv += v.size();
| ^
towns.cpp:116:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
116 | for (auto& [k, v] : by_uh) {
| ^
towns.cpp:116:20: warning: declaration of 'v' shadows a previous local [-Wshadow]
116 | for (auto& [k, v] : by_uh) {
| ^
towns.cpp:28:7: note: shadowed declaration is here
28 | int v = 0;
| ^
towns.cpp:117:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
117 | if (k < uv - r) cu += v.size();
| ^
towns.cpp:118:37: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
118 | if (k == uv - r) cr += v.size();
| ^
towns.cpp:119:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
119 | if (k > uv - r) cv += v.size();
| ^
towns.cpp:14:28: warning: unused parameter 'sub' [-Wunused-parameter]
14 | int hubDistance(int n, int sub) {
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
344 KB |
Output is correct |
| 2 |
Correct |
7 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
9 ms |
528 KB |
Output is correct |
| 5 |
Correct |
9 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
348 KB |
Output is correct |
| 2 |
Correct |
7 ms |
348 KB |
Output is correct |
| 3 |
Correct |
9 ms |
348 KB |
Output is correct |
| 4 |
Correct |
9 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
