結果
| 問題 | No.1976 Cut then Connect |
| ユーザー |
👑  emthrm
|
| 提出日時 | 2022-06-10 23:49:33 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,762 bytes |
| コンパイル時間 | 2,479 ms |
| コンパイル使用メモリ | 216,604 KB |
| 実行使用メモリ | 20,888 KB |
| 最終ジャッジ日時 | 2023-10-21 05:53:43 |
| 合計ジャッジ時間 | 5,617 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,348 KB |
| testcase_01 | AC | 2 ms
4,348 KB |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | AC | 2 ms
4,348 KB |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
ソースコード
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 1000000007;
// constexpr int MOD = 998244353;
constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};
constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};
constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U>
inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
IOSetup() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
std::cout << fixed << setprecision(20);
}
} iosetup;
template <typename CommutativeSemigroup, typename E, typename F, typename G>
std::vector<CommutativeSemigroup> rerooting_dp(
const std::vector<std::vector<int>>& graph,
const std::vector<CommutativeSemigroup>& def,
const E merge, const F f, const G g) {
const int n = graph.size();
if (n == 0) return {};
if (n == 1) return {g(def[0], 0)};
std::vector<std::vector<CommutativeSemigroup>> children(n);
const std::function<CommutativeSemigroup(const int, const int)> dfs1 =
[&graph, &def, merge, f, g, &children, &dfs1](
const int par, const int ver) -> CommutativeSemigroup {
children[ver].reserve(graph[ver].size());
CommutativeSemigroup dp = def[ver];
for (const int e : graph[ver]) {
if (e == par) {
children[ver].emplace_back();
} else {
children[ver].emplace_back(f(dfs1(ver, e), ver, e));
dp = merge(dp, children[ver].back());
}
}
return g(dp, ver);
};
dfs1(-1, 0);
std::vector<CommutativeSemigroup> dp = def;
const std::function<void(const int, const int,
const CommutativeSemigroup&)> dfs2 =
[&graph, &def, merge, f, g, &children, &dp, &dfs2](
const int par, const int ver, const CommutativeSemigroup& m) -> void {
const int c = graph[ver].size();
for (int i = 0; i < c; ++i) {
if (graph[ver][i] == par) {
children[ver][i] = f(m, ver, graph[ver][i]);
break;
}
}
std::vector<CommutativeSemigroup> left{def[ver]}, right;
left.reserve(c);
for (int i = 0; i < c - 1; ++i) {
left.emplace_back(merge(left[i], children[ver][i]));
}
dp[ver] = g(merge(left.back(), children[ver].back()), ver);
if (c >= 2) {
right.reserve(c - 1);
right.emplace_back(children[ver].back());
for (int i = c - 2; i > 0; --i) {
right.emplace_back(merge(children[ver][i], right[c - 2 - i]));
}
std::reverse(right.begin(), right.end());
}
for (int i = 0; i < c; ++i) {
if (graph[ver][i] != par) {
dfs2(ver, graph[ver][i],
g(i + 1 == c ? left[i] : merge(left[i], right[i]), ver));
}
}
};
dfs2(-1, 0, CommutativeSemigroup());
return dp;
}
int main() {
int n; cin >> n;
vector<vector<int>> graph(n);
REP(_, n - 1) {
int u, v; cin >> u >> v; --u; --v;
graph[u].emplace_back(v);
graph[v].emplace_back(u);
}
vector<vector<pair<int, int>>> children(n), diameter(n);
auto f = [&](auto&& f, int par, int ver) -> void {
for (int e : graph[ver]) {
if (e == par) continue;
f(f, ver, e);
if (children[e].empty()) {
children[ver].emplace_back(1, e);
diameter[ver].emplace_back(0, e);
} else {
children[ver].emplace_back(children[e].front().first + 1, e);
if (children[e].size() == 1) {
diameter[ver].emplace_back(max(children[e].front().first, diameter[e].front().first), e);
} else if (children[e].size() >= 2) {
diameter[ver].emplace_back(max(children[e][0].first + children[e][1].first, diameter[e].front().first), e);
}
}
}
sort(ALL(children[ver]), greater<pair<int, int>>());
sort(ALL(diameter[ver]), greater<pair<int, int>>());
};
f(f, -1, 0);
// cout << "[children]\n";
// REP(i, n) {
// cout << i << ':';
// for (const auto [v, e] : children[i]) {
// cout << " {" << v << ',' << e << '}';
// }
// cout << '\n';
// }
// cout << "[diameter]\n";
// REP(i, n) {
// cout << i << ':';
// for (const auto [v, e] : diameter[i]) {
// cout << " {" << v << ',' << e << '}';
// }
// cout << '\n';
// }
auto g = [&](auto&& g, int par, int ver, int dp1, int dp2) -> void {
if (par != -1) {
children[ver].emplace_back(dp1, par);
diameter[ver].emplace_back(dp2, par);
}
sort(ALL(children[ver]), greater<pair<int, int>>());
sort(ALL(diameter[ver]), greater<pair<int, int>>());
for (int e : graph[ver]) {
if (e == par) continue;
int nxt_dp1 = 1;
if (children[ver].front().second != e) {
nxt_dp1 = children[ver].front().first + 1;
} else if (children[ver].size() >= 2) {
nxt_dp1 = children[ver][1].first + 1;
}
int nxt_dp2 = 0;
if (children[ver].size() == 2) {
if (children[ver].front().second == e) {
nxt_dp2 = children[ver][1].first;
} else {
nxt_dp2 = children[ver].front().first;
}
} else if (children[ver].size() >= 3) {
if (children[ver].front().second == e) {
nxt_dp2 = children[ver][1].first + children[ver][2].first;
} else if (children[ver][1].second == e) {
nxt_dp2 = children[ver].front().first + children[ver][2].first;
} else {
nxt_dp2 = children[ver].front().first + children[ver][1].first;
}
}
int nxt_dp3 = 0;
if (diameter[ver].front().second != e) {
nxt_dp3 = diameter[ver].front().first;
} else if (diameter[ver].size() >= 2) {
nxt_dp3 = diameter[ver][1].first;
}
g(g, ver, e, nxt_dp1, max(nxt_dp2, nxt_dp3));
}
};
g(g, -1, 0, 0, 0);
// cout << "[children]\n";
// REP(i, n) {
// cout << i << ':';
// for (const auto [v, e] : children[i]) {
// cout << " {" << v << ',' << e << '}';
// }
// cout << '\n';
// }
// cout << "[diameter]\n";
// REP(i, n) {
// cout << i << ':';
// for (const auto [v, e] : diameter[i]) {
// cout << " {" << v << ',' << e << '}';
// }
// cout << '\n';
// }
int ans = INF;
REP(i, n) {
for (int e : graph[i]) {
int child_diameter = 0;
if (children[e].front().second != i) {
child_diameter = children[e].front().first;
} else if (diameter[e].size() >= 2) {
child_diameter = children[e][1].first;
}
int root_diameter = 0;
if (children[i].size() == 2) {
if (children[i].front().second == e) {
root_diameter = children[i][1].first;
} else {
root_diameter = children[i].front().first;
}
} else if (children[i].size() >= 3) {
if (children[i].front().second == e) {
root_diameter = children[i][1].first + children[i][2].first;
} else if (children[i][1].second == e) {
root_diameter = children[i].front().first + children[i][2].first;
} else {
root_diameter = children[i].front().first + children[i][1].first;
}
}
// cout << i << ": " << root_diameter << ' ' << child_diameter << '\n';
chmin(ans, (root_diameter + 1) / 2 + (child_diameter + 1) / 2 + 1);
}
}
cout << ans << '\n';
return 0;
}