結果

問題 No.1976 Cut then Connect
ユーザー ChanyuhChanyuh
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0