結果

問題 No.1976 Cut then Connect
ユーザー shino16
提出日時 2022-03-27 16:57:30
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,657 bytes
コンパイル時間 13,198 ms
コンパイル使用メモリ 300,424 KB
最終ジャッジ日時 2025-01-28 13:06:24
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 11 RE * 20
権限があれば一括ダウンロードができます

ソースコード

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

#line 2 "lib/prelude.hpp"
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep2(i, m, n) for (auto i = (m); i < (n); i++)
#define rep(i, n) rep2(i, 0, n)
#define repr2(i, m, n) for (auto i = (n); i-- > (m);)
#define repr(i, n) repr2(i, 0, n)
#define all(x) begin(x), end(x)
#line 2 "main.cpp"
const int MaxN = 1000;
int n;
vector<int> G[MaxN];
// paths[v] = {(v-u-で始まる最長パス長, u)} 降順
vector<pair<int, int>> paths[MaxN];
// longest[v] = {(uの部分木内の最長パス長, u)} 降順
vector<pair<int, int>> longest[MaxN];
int ans;
void dfs1(int v, int p) {
  for (auto u : G[v])
    if (u != p) {
      dfs1(u, v);
      paths[v].emplace_back(paths[u][0].first + 1, u);
      longest[v].emplace_back(
          max(longest[u][0].first, paths[u][0].first + paths[u][1].first), u);
    }
  paths[v].emplace_back(0, -1);
  paths[v].emplace_back(0, -1);
  sort(paths[v].begin(), paths[v].end(), greater{});
  paths[v].resize(3);
  longest[v].emplace_back(0, -1);
  sort(longest[v].begin(), longest[v].end(), greater{});
  longest[v].resize(2);
}
void dfs2(int v, int p) {
  for (auto u : G[v])
    if (u != p) {
      // 辺{u,v}を消す
      int u_len =
          max(longest[u][0].first, paths[u][0].first + paths[u][1].first);
      int i1 = u == paths[v][0].second ? 1 : 0;
      int i2 = u == paths[v][i1 + 1].second ? i1 + 2 : i1 + 1;
      int j = u == longest[v][0].second ? 1 : 0;
      int v_len =
          max(longest[v][j].first, paths[v][i1].first + paths[v][i2].first);
      ans = max(ans, u_len + v_len + 2);
      pair<int, int> val1(-1, -1), val2(-1, -1);
      auto it1 = find_if(all(paths[v]), [&](auto&& a) { return a.second == u; });
      if (it1 != paths[v].end()) val1 = *it1, paths[v].erase(it1);
      auto it2 = find_if(all(longest[v]), [&](auto&& a) { return a.second == u; });
      if (it2 != longest[v].end()) val2 = *it2, longest[v].erase(it2);
      paths[u].emplace_back(paths[v][0].first + 1, v);
      longest[u].emplace_back(
          max(longest[v][0].first, paths[v][0].first + paths[v][1].first), v);
      sort(paths[u].begin(), paths[u].end(), greater{});
      sort(longest[u].begin(), longest[u].end(), greater{});
      dfs2(u, v);
      if (val1.first != -1) paths[v].insert(it1, val1);
      if (val2.first != -1) longest[v].insert(it2, val2);
    }
}
int main() {
  scanf("%d", &n);
  rep(_, n-1) {
    int u, v; scanf("%d%d", &u, &v), u--, v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs1(0, -1);
  ans = 0;
  dfs2(0, -1);
  printf("%d\n", ans);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0