結果

問題 No.1976 Cut then Connect
ユーザー shino16shino16
提出日時 2022-05-31 04:46:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,744 bytes
コンパイル時間 4,022 ms
コンパイル使用メモリ 237,504 KB
実行使用メモリ 24,760 KB
最終ジャッジ日時 2023-10-21 00:28:56
合計ジャッジ時間 7,456 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 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 3 "lib/ds/dsu.hpp"

class dsu {
 public:
  dsu(int n) : par(n, -1), count_(n) {}
  int size() const { return par.size(); }
  int count() const { return count_; }
  void clear() {
    fill(par.begin(), par.end(), -1);
    count_ = size();
  }
  int find(int x) { return par[x] < 0 ? x : par[x] = (int)find(par[x]); }
  bool same(int x, int y) { return find(x) == find(y); }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (par[x] > par[y]) swap(x, y);
    par[x] += par[y], par[y] = (int)x;
    count_--;
    return true;
  }
  vector<vector<int>> groups() {
    vector<vector<int>> res(size());
    for (int x = 0; x < size(); x++) res[find(x)].push_back(x);
    res.erase(remove_if(all(res), [](const auto& v) { return v.empty(); }),
              res.end());
    return res;
  }

 private:
  vector<int> par;
  int count_;
};
#line 3 "main.cpp"

const int MaxN = 100000;

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 = min(ans, (u_len + 1) / 2 + (v_len + 1) / 2 + 1);

      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);
  assert(2 <= n && n <= 100000);
  dsu dsu(n);
  rep(_, n-1) {
    int u, v; scanf("%d%d", &u, &v);
    assert(1 <= u && u <= n);
    assert(1 <= v && v <= n);
    assert(u != v);
    u--, v--;
    assert(dsu.unite(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