結果
| 問題 | No.2677 Minmax Independent Set |
| コンテスト | |
| ユーザー |
 Jinapetto
|
| 提出日時 | 2024-03-20 12:38:42 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,005 bytes |
| 記録 | |
| コンパイル時間 | 2,232 ms |
| コンパイル使用メモリ | 325,748 KB |
| 最終ジャッジ日時 | 2026-04-16 11:09:17 |
| 合計ジャッジ時間 | 3,898 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_1 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_algobase.h:64,
from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/algorithm:62,
from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/x86_64-pc-linux-gnu/bits/stdc++.h:53,
from main.cpp:1:
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_pair.h: In substitution of 'template<class _U1, class _U2> requires _S_constructible<const _U1&, const _U2&>() && _S_dangles<const _U1&, const _U2&>() constexpr std::pair<int, int>::pair(const std::pair<_T1, _T2>&) [with _U1 = int; _U2 = int]':
main.cpp:97:31: required from 'std::vector<_ValT> RerootingDP<E, V, merge, e, put_edge, put_vertex>::reroot() [with E = std::pair<int, int>; V = std::pair<int, int>; E (* merge)(E, E) = merge; E (* e)() = e; E (* put_edge)(V, int) = put_e; V (* put_vertex)(E, int) = put_v]'
97 | rui[i] = merge(outs[le+i],rui[i+1]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
main.cpp:162:22: required from here
162 | auto ret = dp.reroot();
| ~~~~~~~~~^~
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_pair.h:490:2: required by the constraints of 'template<class _T1, class _T2> template<class _U1, class _U2> requires _S_constructible<const _U1&, const _U2&>() && _S_dangles<const _U1&, const _U2&>() constexpr std::pair<_T1, _T2>::pair(const std::pair<_U1, _U2>&)'
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_pair.h:488:53: error: 'static constexpr bool std::pair<_T1, _T2>::_S_dangles() [with _U1 = const int&; _U2 = const int&; _T1 = int; _T2 = int]' used before its definition
488 | && (_S_dangles<const _U1&, const _U2&>())
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_pair.h: In substitution
ソースコード
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
//using mint = modint998244353;
//多倍長整数//
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;
//using Bint = mp::cpp_int;
const int INF = 1e9;
const int MOD = 998244353;
const long long LINF = 4e18;
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vvvvi = vector<vector<vector<vector<int>>>>;
using vvl = vector<vector<long long>>;
using vvvl = vector<vector<vector<long long>>>;
using vvvvl = vector<vector<vector<vector<long long>>>>;
using vvc = vector<vector<char>>;
using vvb = vector<vector<bool>>;
using vvvb = vector<vector<vector<bool>>>;
using vvvvb = vector<vector<vector<vector<bool>>>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define dump(x) cout << #x << " = " << (x) << endl;
#define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl
#define ALL(obj) (obj).begin(),(obj).end()
//https://trap.jp/post/1702/
template <class E, class V, E (*merge)(E, E), E (*e)(), E (*put_edge)(V, int), V (*put_vertex)(E, int)>
struct RerootingDP {
struct edge {
int to, idx, xdi;
};
RerootingDP(int n_ = 0) : n(n_), inner_edge_id(0) {
es.resize(2*n-2);
start.resize(2*n-2);
if (n == 1) es_build();
}
void add_edge(int u, int v, int idx, int xdi){
start[inner_edge_id] = u;
es[inner_edge_id] = {v,idx,xdi};
inner_edge_id++;
start[inner_edge_id] = v;
es[inner_edge_id] = {u,xdi,idx};
inner_edge_id++;
if (inner_edge_id == 2*n-2){
es_build();
}
}
vector<V> build(int root_ = 0){
root = root_;
vector<V> subdp(n); subdp[0] = put_vertex(e(),0);
outs.resize(n);
vector<int> geta(n+1,0);
for (int i = 0; i < n; i++) geta[i+1] = start[i+1] - start[i] - 1;
geta[root+1]++;
for (int i = 0; i < n; i++) geta[i+1] += geta[i];
auto dfs = [&](auto sfs, int v, int f) -> void {
E val = e();
for (int i = start[v]; i < start[v+1]; i++){
if (es[i].to == f){
swap(es[start[v+1]-1],es[i]);
}
if (es[i].to == f) continue;
sfs(sfs,es[i].to,v);
E nval = put_edge(subdp[es[i].to],es[i].idx);
outs[geta[v]++] = nval;
val = merge(val,nval);
}
subdp[v] = put_vertex(val, v);
};
dfs(dfs,root,-1);
return subdp;
}
vector<V> reroot(){
vector<E> reverse_edge(n);
reverse_edge[root] = e();
vector<V> answers(n);
auto dfs = [&](auto sfs, int v) -> void {
int le = outs_start(v);
int ri = outs_start(v+1);
int siz = ri - le;
vector<E> rui(siz+1);
rui[siz] = e();
for (int i = siz-1; i >= 0; i--){
rui[i] = merge(outs[le+i],rui[i+1]);
}
answers[v] = put_vertex(merge(rui[0],reverse_edge[v]),v);
E lui = e();
for (int i = 0; i < siz; i++){
V rdp = put_vertex(merge(merge(lui,rui[i+1]),reverse_edge[v]),v);
reverse_edge[es[start[v]+i].to] = put_edge(rdp,es[start[v]+i].xdi);
lui = merge(lui,outs[le+i]);
sfs(sfs,es[start[v]+i].to);
}
};
dfs(dfs,root);
return answers;
}
private:
int n, root, inner_edge_id;
vector<E> outs;
vector<edge> es;
vector<int> start;
int outs_start(int v){
int res = start[v] - v;
if (root < v) res++;
return res;
}
void es_build(){
vector<edge> nes(2*n-2);
vector<int> nstart(n+2,0);
for (int i = 0; i < 2*n-2; i++) nstart[start[i]+2]++;
for (int i = 0; i < n; i++) nstart[i+1] += nstart[i];
for (int i = 0; i < 2*n-2; i++) nes[nstart[start[i]+1]++] = es[i];
swap(es,nes);
swap(start,nstart);
}
};
pair<int,int> merge(pair<int,int> a,pair<int,int> b){
return {a.first + b.first,a.second + b.second};
}
pair<int,int> e(){
return make_pair(0,0);
}
pair<int,int> put_e(pair<int,int> x,int i){
return {x.first,max(x.first,x.second)};
}
pair<int,int> put_v(pair<int,int> x,int i){
return {x.second,x.first + 1};
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
RerootingDP<pair<int,int>, pair<int,int>,merge, e,put_e,put_v> dp(n);
rep(i,n - 1){
int a,b;
cin >> a >> b;
a--;b--;
dp.add_edge(a,b,i,i + n);
}
int ans = INF;
dp.build();
auto ret = dp.reroot();
// cout << endl;
// rep(i,n) cout << ret[i].first << ' ' << ret[i].second << endl;
rep(i,n){
ans = min(ans,ret[i].second);
}
cout << ans << endl;
return 0;
}