結果
問題 | No.2677 Minmax Independent Set |
ユーザー | 👑 potato167 |
提出日時 | 2024-03-15 21:43:59 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 297 ms / 2,000 ms |
コード長 | 4,398 bytes |
コンパイル時間 | 2,839 ms |
コンパイル使用メモリ | 221,348 KB |
実行使用メモリ | 84,252 KB |
最終ジャッジ日時 | 2024-03-15 21:44:12 |
合計ジャッジ時間 | 13,195 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,548 KB |
testcase_01 | AC | 2 ms
6,548 KB |
testcase_02 | AC | 2 ms
6,548 KB |
testcase_03 | AC | 2 ms
6,548 KB |
testcase_04 | AC | 2 ms
6,548 KB |
testcase_05 | AC | 248 ms
38,692 KB |
testcase_06 | AC | 247 ms
41,892 KB |
testcase_07 | AC | 247 ms
42,532 KB |
testcase_08 | AC | 260 ms
41,636 KB |
testcase_09 | AC | 241 ms
44,324 KB |
testcase_10 | AC | 160 ms
35,084 KB |
testcase_11 | AC | 157 ms
35,084 KB |
testcase_12 | AC | 272 ms
84,252 KB |
testcase_13 | AC | 274 ms
51,032 KB |
testcase_14 | AC | 232 ms
52,664 KB |
testcase_15 | AC | 290 ms
61,408 KB |
testcase_16 | AC | 260 ms
34,968 KB |
testcase_17 | AC | 290 ms
34,972 KB |
testcase_18 | AC | 166 ms
23,424 KB |
testcase_19 | AC | 192 ms
27,196 KB |
testcase_20 | AC | 64 ms
11,648 KB |
testcase_21 | AC | 217 ms
29,692 KB |
testcase_22 | AC | 12 ms
6,548 KB |
testcase_23 | AC | 2 ms
6,548 KB |
testcase_24 | AC | 2 ms
6,548 KB |
testcase_25 | AC | 2 ms
6,548 KB |
testcase_26 | AC | 2 ms
6,548 KB |
testcase_27 | AC | 2 ms
6,548 KB |
testcase_28 | AC | 140 ms
35,304 KB |
testcase_29 | AC | 297 ms
65,296 KB |
testcase_30 | AC | 2 ms
6,548 KB |
testcase_31 | AC | 2 ms
6,548 KB |
testcase_32 | AC | 2 ms
6,548 KB |
testcase_33 | AC | 2 ms
6,548 KB |
testcase_34 | AC | 2 ms
6,548 KB |
testcase_35 | AC | 2 ms
6,548 KB |
testcase_36 | AC | 2 ms
6,548 KB |
testcase_37 | AC | 2 ms
6,548 KB |
testcase_38 | AC | 3 ms
6,548 KB |
testcase_39 | AC | 3 ms
6,548 KB |
testcase_40 | AC | 4 ms
6,548 KB |
testcase_41 | AC | 6 ms
6,548 KB |
testcase_42 | AC | 11 ms
6,548 KB |
testcase_43 | AC | 23 ms
7,296 KB |
testcase_44 | AC | 57 ms
11,264 KB |
testcase_45 | AC | 122 ms
19,072 KB |
testcase_46 | AC | 287 ms
34,792 KB |
testcase_47 | AC | 287 ms
35,232 KB |
testcase_48 | AC | 288 ms
35,232 KB |
testcase_49 | AC | 284 ms
35,476 KB |
testcase_50 | AC | 54 ms
15,060 KB |
testcase_51 | AC | 5 ms
6,548 KB |
testcase_52 | AC | 132 ms
29,168 KB |
testcase_53 | AC | 129 ms
27,152 KB |
testcase_54 | AC | 5 ms
6,548 KB |
testcase_55 | AC | 170 ms
33,844 KB |
testcase_56 | AC | 173 ms
34,312 KB |
testcase_57 | AC | 166 ms
34,364 KB |
testcase_58 | AC | 170 ms
34,180 KB |
testcase_59 | AC | 172 ms
34,612 KB |
testcase_60 | AC | 102 ms
36,020 KB |
testcase_61 | AC | 121 ms
34,584 KB |
testcase_62 | AC | 116 ms
44,964 KB |
testcase_63 | AC | 135 ms
61,780 KB |
ソースコード
#include <bits/stdc++.h> #pragma GCC optimize("unroll-loops") using namespace std; using std::cout; using std::cin; using std::endl; using ll=long long; using ld=long double; const ll ILL=2167167167167167167; const int INF=2100000000; const int mod=998244353; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define all(p) p.begin(),p.end() template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>; template<class T> ll LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template<class T> ll UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template<class T> bool chmin(T &a,T b){if(a>b){a=b;return 1;}else return 0;} template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;} template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());} template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} void yneos(bool a,bool upp=0){if(a) cout<<(upp?"YES\n":"Yes\n"); else cout<<(upp?"NO\n":"No\n");} template<class T> void vec_out(vector<T> &p,int ty=0){ if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";} else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}} template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;} template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;} template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;} int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;} //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 from, to, idx, rev_idx; }; RerootingDP (int _n = 0) : n(_n) { es.resize(n);} void add_edge(int u, int v, int idx1, int idx2){ es[u].push_back({u,v,idx1,idx2}); es[v].push_back({v,u,idx2,idx1}); } V build(int v = 0){ root = v; vis.resize(n,0); outs.resize(n); return dfs(root); } vector<V> reroot(){ reverse_edge.resize(n); reverse_edge[root] = e(); answers.resize(n); bfs(root); return answers; } private: int n, root; vector<vector<edge>> es; vector<int> vis; vector<vector<E>> outs; vector<E> reverse_edge; vector<V> answers; V dfs(int v){ vis[v]++; E val = e(); for (auto &p : es[v]){ if (vis[p.to] > 0 && p.to != es[v].back().to) swap(p,es[v].back()); if (vis[p.to] > 0) continue; E nval = put_edge(dfs(p.to),p.idx); outs[v].emplace_back(nval); val = merge(val,nval); } return put_vertex(val,v); } void bfs(int v){ int siz = outs[v].size(); vector<E> lui(siz+1), rui(siz+1); lui[0] = e(), rui[siz] = e(); for (int i = 0; i < siz; i++) lui[i+1] = merge(lui[i],outs[v][i]); for (int i = siz-1; i >= 0; i--) rui[i] = merge(outs[v][i],rui[i+1]); for (int i = 0; i < siz; i++){ reverse_edge[es[v][i].to] = put_edge(put_vertex(merge(merge(lui[i],rui[i+1]),reverse_edge[v]),v),es[v][i].rev_idx); bfs(es[v][i].to); } answers[v] = put_vertex(merge(lui[siz],reverse_edge[v]), v); } }; struct reroot_F{ int black; int white; int large; }; reroot_F merge(reroot_F a, reroot_F b){ return {a.black+b.black,a.white+b.white,a.large+b.large}; } reroot_F e(){ return {0,0,0}; } reroot_F put_edge(reroot_F v, int i){ return v; } reroot_F put_vertex(reroot_F e, int v){ e.black=e.white+1; e.white=e.large; e.large=max(e.black,e.white); return e; } #define reroot_calc reroot_F,reroot_F,merge,e,put_edge,put_vertex void solve(); // oddloop int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t=1; //cin>>t; rep(i,0,t) solve(); } void solve(){ int N; cin>>N; RerootingDP<reroot_calc> G(N); rep(i,0,N-1){ int a,b; cin>>a>>b; G.add_edge(a-1,b-1,0,0); } G.build(); auto res=G.reroot(); int ans=INF; rep(i,0,N) chmin(ans,res[i].black); cout<<ans<<"\n"; }