結果

問題 No.1976 Cut then Connect
ユーザー shino16shino16
提出日時 2022-03-27 16:55:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,657 bytes
コンパイル時間 3,721 ms
コンパイル使用メモリ 234,324 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-20 23:14:33
合計ジャッジ時間 7,415 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
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 WA -
testcase_31 WA -
testcase_32 WA -
権限があれば一括ダウンロードができます

ソースコード

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[v].begin(), paths[v].end(), greater{});
      sort(longest[v].begin(), longest[v].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);
}
0