結果
問題 | No.2677 Minmax Independent Set |
ユーザー | 沙耶花 |
提出日時 | 2024-03-15 22:10:04 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 335 ms / 2,000 ms |
コード長 | 2,500 bytes |
コンパイル時間 | 4,821 ms |
コンパイル使用メモリ | 272,652 KB |
実行使用メモリ | 82,276 KB |
最終ジャッジ日時 | 2024-03-15 22:10:25 |
合計ジャッジ時間 | 16,017 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 2 ms
6,676 KB |
testcase_04 | AC | 2 ms
6,676 KB |
testcase_05 | AC | 267 ms
35,428 KB |
testcase_06 | AC | 262 ms
36,196 KB |
testcase_07 | AC | 273 ms
36,836 KB |
testcase_08 | AC | 268 ms
38,372 KB |
testcase_09 | AC | 270 ms
41,060 KB |
testcase_10 | AC | 225 ms
35,768 KB |
testcase_11 | AC | 220 ms
35,768 KB |
testcase_12 | AC | 316 ms
82,276 KB |
testcase_13 | AC | 320 ms
50,256 KB |
testcase_14 | AC | 288 ms
50,048 KB |
testcase_15 | AC | 335 ms
60,332 KB |
testcase_16 | AC | 330 ms
29,540 KB |
testcase_17 | AC | 334 ms
29,540 KB |
testcase_18 | AC | 193 ms
20,112 KB |
testcase_19 | AC | 234 ms
23,108 KB |
testcase_20 | AC | 62 ms
10,368 KB |
testcase_21 | AC | 263 ms
25,316 KB |
testcase_22 | AC | 12 ms
6,676 KB |
testcase_23 | AC | 3 ms
6,676 KB |
testcase_24 | AC | 2 ms
6,676 KB |
testcase_25 | AC | 2 ms
6,676 KB |
testcase_26 | AC | 2 ms
6,676 KB |
testcase_27 | AC | 2 ms
6,676 KB |
testcase_28 | AC | 201 ms
36,864 KB |
testcase_29 | AC | 314 ms
62,808 KB |
testcase_30 | AC | 2 ms
6,676 KB |
testcase_31 | AC | 2 ms
6,676 KB |
testcase_32 | AC | 2 ms
6,676 KB |
testcase_33 | AC | 2 ms
6,676 KB |
testcase_34 | AC | 2 ms
6,676 KB |
testcase_35 | AC | 2 ms
6,676 KB |
testcase_36 | AC | 2 ms
6,676 KB |
testcase_37 | AC | 2 ms
6,676 KB |
testcase_38 | AC | 3 ms
6,676 KB |
testcase_39 | AC | 3 ms
6,676 KB |
testcase_40 | AC | 4 ms
6,676 KB |
testcase_41 | AC | 6 ms
6,676 KB |
testcase_42 | AC | 11 ms
6,676 KB |
testcase_43 | AC | 24 ms
6,676 KB |
testcase_44 | AC | 53 ms
9,984 KB |
testcase_45 | AC | 126 ms
16,384 KB |
testcase_46 | AC | 293 ms
29,184 KB |
testcase_47 | AC | 301 ms
29,412 KB |
testcase_48 | AC | 299 ms
29,412 KB |
testcase_49 | AC | 299 ms
29,668 KB |
testcase_50 | AC | 68 ms
15,380 KB |
testcase_51 | AC | 6 ms
6,676 KB |
testcase_52 | AC | 167 ms
31,108 KB |
testcase_53 | AC | 156 ms
27,672 KB |
testcase_54 | AC | 5 ms
6,676 KB |
testcase_55 | AC | 263 ms
33,452 KB |
testcase_56 | AC | 265 ms
33,788 KB |
testcase_57 | AC | 281 ms
33,812 KB |
testcase_58 | AC | 271 ms
33,564 KB |
testcase_59 | AC | 266 ms
33,788 KB |
testcase_60 | AC | 113 ms
30,052 KB |
testcase_61 | AC | 120 ms
30,180 KB |
testcase_62 | AC | 128 ms
41,700 KB |
testcase_63 | AC | 144 ms
59,364 KB |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 int ans = Inf32; template <class Ss, Ss (*op0)(Ss, Ss), Ss (*e)(), class Sv, Ss (*op1)(Sv, Ss), class Se, Ss (*op2)(Se, Ss)> struct rerooting{ int n; vector<vector<int>> to; vector<vector<Se>> edge; vector<Ss> subtree,answer; vector<Sv> vertex; rerooting(int _n){ n = _n; to.resize(n); edge.resize(n); subtree.resize(n,e()); answer.resize(n,e()); vertex.resize(n); } rerooting(vector<Sv> v){ n = v.size(); to.resize(n); edge.resize(n); subtree.resize(n,e()); answer.resize(n,e()); vertex = v; } void add_directed_edge(int u,int v,Se x){ to[u].push_back(v); edge[u].push_back(x); } void add_edge(int u,int v,Se x){ add_directed_edge(u,v,x); add_directed_edge(v,u,x); } void solve(){ dfs(0,-1); redfs(0,-1,e()); } void dfs(int cur,int par){ Ss temp = e(); for(int i=0;i<to[cur].size();i++){ int nxt = to[cur][i]; if(nxt==par)continue; dfs(nxt,cur); temp = op0(temp, op2(edge[cur][i], subtree[nxt])); } subtree[cur] = op1(vertex[cur], temp); } void redfs(int cur, int par, Ss ps){ vector<Ss> P(to[cur].size()+1,e()); rep(i,to[cur].size()){ int nxt = to[cur][i]; if(nxt!=par)P[i+1] = op2(edge[cur][i], subtree[nxt]); else P[i+1] = op2(edge[cur][i], ps); } { int tt= 0; rep(i,P.size()){ tt += P[i].first; } ans = min(ans,tt+1); } vector<Ss> S(P.rbegin(),P.rend()-1); S.insert(S.begin(),e()); rep(i,to[cur].size()){ P[i+1] = op0(P[i], P[i+1]); S[i+1] = op0(S[i+1], S[i]); } answer[cur] = op1(vertex[cur], P.back()); for(int i=0;i<to[cur].size();i++){ int nxt = to[cur][i]; if(nxt!=par){ redfs(nxt,cur,op1(vertex[cur], op0(P[i],S[to[cur].size()-1-i]))); } } } }; using P = pair<int,int>; P op0(P a,P b){ return make_pair(max({a.first+b.first}),max({a.first+b.second,a.second+b.first,a.second+b.second})); } P e(){ return make_pair(0,0); } P op1(int a,P b){ return make_pair(max(b.first,b.second),b.first + 1); } P op2(int a,P b){ return b; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; rerooting<P,op0,e,int,op1,int,op2> R(n); rep(i,n-1){ int a,b; cin>>a>>b; a--,b--; R.add_edge(a,b,0); } R.solve(); cout<<ans<<endl; return 0; }