| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1015368 |
2024-07-06T09:42:17 Z |
우민규(#10889) |
Towns (IOI15_towns) |
C++14 |
|
13 ms |
1116 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;
if (uh > ux) continue;
r = min(r, max(uh, uv - uh));
by_uh[uh].push_back(i);
}
// 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 uv = get_distance(u, v);
int uh = (ua + uv - ab) / 2;
return uh != req_uh;
};
// true -> balanced
// false -> not
auto determine_child = [&](int uh) -> bool {
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, 0});
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 same_subtree_count = 0;
for (auto [rep, count] : mounds) {
if (is_same_subtree(rep, majority_node, uh)) {
same_subtree_count += count;
}
}
for (auto v : diff_from_mound) {
if (is_same_subtree(majority_node, v, uh)) {
same_subtree_count += 1;
}
}
return same_subtree_count <= 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 (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:60:9: warning: declaration of 'uv' shadows a previous local [-Wshadow]
60 | int uv = get_distance(u, v);
| ^~
towns.cpp:20:7: note: shadowed declaration is here
20 | int uv = get_distance(0, u);
| ^~
towns.cpp: In lambda function:
towns.cpp:71:15: warning: declaration of 'v' shadows a previous local [-Wshadow]
71 | for (auto v : rc) {
| ^
towns.cpp:28:7: note: shadowed declaration is here
28 | int v = 0;
| ^
towns.cpp:88:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
88 | for (auto [rep, count] : mounds) {
| ^
towns.cpp:88:21: warning: declaration of 'count' shadows a previous local [-Wshadow]
88 | for (auto [rep, count] : mounds) {
| ^~~~~
towns.cpp:70:9: note: shadowed declaration is here
70 | int count = 0;
| ^~~~~
towns.cpp:93:15: warning: declaration of 'v' shadows a previous local [-Wshadow]
93 | 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:103:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
103 | for (auto& [k, v] : by_uh) {
| ^
towns.cpp:103:20: warning: declaration of 'v' shadows a previous local [-Wshadow]
103 | for (auto& [k, v] : by_uh) {
| ^
towns.cpp:28:7: note: shadowed declaration is here
28 | int v = 0;
| ^
towns.cpp:104:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
104 | if (k < r) cu += v.size();
| ^
towns.cpp:105:32: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
105 | if (k == r) cr += v.size();
| ^
towns.cpp:106:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
106 | if (k > r) cv += v.size();
| ^
towns.cpp:115:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
115 | for (auto& [k, v] : by_uh) {
| ^
towns.cpp:115:20: warning: declaration of 'v' shadows a previous local [-Wshadow]
115 | for (auto& [k, v] : by_uh) {
| ^
towns.cpp:28:7: note: shadowed declaration is here
28 | int v = 0;
| ^
towns.cpp:116:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
116 | if (k < uv - r) cu += v.size();
| ^
towns.cpp:117:37: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
117 | if (k == uv - r) cr += v.size();
| ^
towns.cpp:118:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
118 | 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 |
9 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
7 ms |
860 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
10 ms |
840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
10 ms |
856 KB |
Output is correct |
| 4 |
Correct |
10 ms |
860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
