結果
問題 | No.1976 Cut then Connect |
ユーザー | Chanyuh |
提出日時 | 2022-06-28 15:36:54 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,566 bytes |
コンパイル時間 | 1,764 ms |
コンパイル使用メモリ | 140,808 KB |
実行使用メモリ | 19,336 KB |
最終ジャッジ日時 | 2024-11-21 09:10:36 |
合計ジャッジ時間 | 4,479 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
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 | AC | 6 ms
8,064 KB |
testcase_25 | AC | 6 ms
8,192 KB |
testcase_26 | AC | 6 ms
8,192 KB |
testcase_27 | WA | - |
testcase_28 | AC | 6 ms
8,064 KB |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | AC | 6 ms
8,064 KB |
testcase_32 | AC | 6 ms
8,192 KB |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <ciso646>#include <cmath>#include <complex>#include <cstdio>#include <functional>#include <iomanip>#include <iostream>#include <map>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <tuple>#include <unordered_map>#include <utility>#include <vector>using namespace std;typedef long long ll;const ll mod = 1000000007;const ll INF = (ll)1000000007 * 1000000007;typedef pair<int, int> P;#define rep(i, n) for (int i = 0; i < n; i++)#define per(i, n) for (int i = n - 1; i >= 0; i--)#define Rep(i, sta, n) for (int i = sta; i < n; i++)#define Per(i, sta, n) for (int i = n - 1; i >= sta; i--)typedef long double ld;const ld eps = 1e-8;const ld pi = acos(-1.0);typedef pair<ll, ll> LP;int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};template <class T>using max_heap = priority_queue<T>;template <class T>using min_heap = priority_queue<T, vector<T>, greater<>>;template <class T>bool chmax(T &a, const T &b) {if (a < b) {a = b;return 1;}return 0;}template <class T>bool chmin(T &a, const T &b) {if (b < a) {a = b;return 1;}return 0;}struct edge {int to, id, t;edge() {}edge(int to, int id, int t) : to(to), id(id), t(t) {}};int n;vector<edge> G[200010];int depth[200010], di[200010][2];P max_depth[200010][3];void dfs1(int s, int par, edge pre_e) {if (par != -1) depth[s] = depth[par] + 1;for (edge e : G[s]) {if (e.to == par) continue;dfs1(e.to, s, e);if (max_depth[s][0].first < max_depth[e.to][2].first + 1) {max_depth[s][0] = {max_depth[e.to][2].first + 1, e.id};sort(max_depth[s], max_depth[s] + 3);}if (pre_e.id != -1) chmax(di[pre_e.id][pre_e.t], di[e.id][e.t]);}if (pre_e.id != -1)chmax(di[pre_e.id][pre_e.t], max_depth[s][2].first + max_depth[s][1].first);}void dfs2(int s, int par, edge pre_e, int depth_par) {set<P> v = {max_depth[s][0], max_depth[s][1], max_depth[s][2], {depth_par, pre_e.id}};for (edge e : G[s]) {if (e.to == par) continue;P erased = P(-1, -1);// for (P p : v)// if (p.second == e.id) {// erased = p;// v.erase(p);// }auto it = v.end();it--;int d_first = (*it).first;it--;int d_second = (*it).first;dfs2(e.to, s, e, d_first + 1);chmax(di[e.id][1 - e.t], d_first + d_second);if (erased != P(-1, -1)) v.insert(erased);}}void dfs3(int s, int par, edge pre_e) {for (edge e : G[s]) {if (e.to == par) continue;if (par != -1) chmax(di[e.id][1 - e.t], di[pre_e.id][1 - pre_e.t]);dfs3(e.to, s, e);}}void solve() {cin >> n;rep(i, n - 1) {int a, b;cin >> a >> b;a--;b--;G[a].push_back({b, i, 0});G[b].push_back({a, i, 1});}rep(i, n) rep(j, 3) max_depth[i][j] = P(0, -1);rep(i, n - 1) rep(j, 2) di[i][j] = -1;dfs1(0, -1, {0, -1, -1});// rep(i, n) cout << depth[i] << " ";// cout << "" << endl;// rep(i, n) {// rep(j, 3) cout << max_depth[i][j].first << " ";// cout << "" << endl;// }dfs2(0, -1, {0, -1, -1}, 0);dfs3(0, -1, {0, -1, -1});// rep(i, n - 1) { cout << di[i][0] << " " << di[i][1] << endl; }int ans = mod;rep(i, n - 1) { chmin(ans, 1 + (di[i][0] + 1) / 2 + (di[i][1] + 1) / 2); }cout << ans << endl;}int main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(50);solve();}