結果
問題 | No.2677 Minmax Independent Set |
ユーザー | maeshun |
提出日時 | 2024-03-16 12:15:50 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 352 ms / 2,000 ms |
コード長 | 3,162 bytes |
コンパイル時間 | 4,724 ms |
コンパイル使用メモリ | 272,596 KB |
実行使用メモリ | 80,744 KB |
最終ジャッジ日時 | 2024-03-16 12:16:09 |
合計ジャッジ時間 | 17,383 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 20 ms
19,796 KB |
testcase_01 | AC | 19 ms
19,796 KB |
testcase_02 | AC | 20 ms
19,796 KB |
testcase_03 | AC | 20 ms
19,796 KB |
testcase_04 | AC | 20 ms
19,796 KB |
testcase_05 | AC | 281 ms
39,784 KB |
testcase_06 | AC | 279 ms
40,424 KB |
testcase_07 | AC | 268 ms
40,936 KB |
testcase_08 | AC | 263 ms
42,216 KB |
testcase_09 | AC | 273 ms
44,520 KB |
testcase_10 | AC | 212 ms
37,992 KB |
testcase_11 | AC | 221 ms
37,992 KB |
testcase_12 | AC | 325 ms
80,744 KB |
testcase_13 | AC | 317 ms
52,072 KB |
testcase_14 | AC | 287 ms
52,584 KB |
testcase_15 | AC | 352 ms
61,544 KB |
testcase_16 | AC | 301 ms
35,048 KB |
testcase_17 | AC | 301 ms
35,048 KB |
testcase_18 | AC | 181 ms
29,540 KB |
testcase_19 | AC | 243 ms
31,336 KB |
testcase_20 | AC | 74 ms
23,820 KB |
testcase_21 | AC | 245 ms
32,488 KB |
testcase_22 | AC | 33 ms
20,948 KB |
testcase_23 | AC | 20 ms
19,796 KB |
testcase_24 | AC | 20 ms
19,796 KB |
testcase_25 | AC | 19 ms
19,796 KB |
testcase_26 | AC | 20 ms
19,796 KB |
testcase_27 | AC | 20 ms
19,796 KB |
testcase_28 | AC | 196 ms
38,504 KB |
testcase_29 | AC | 307 ms
63,460 KB |
testcase_30 | AC | 20 ms
19,796 KB |
testcase_31 | AC | 19 ms
19,796 KB |
testcase_32 | AC | 20 ms
19,796 KB |
testcase_33 | AC | 20 ms
19,796 KB |
testcase_34 | AC | 20 ms
19,796 KB |
testcase_35 | AC | 20 ms
19,796 KB |
testcase_36 | AC | 20 ms
19,796 KB |
testcase_37 | AC | 20 ms
19,796 KB |
testcase_38 | AC | 21 ms
19,796 KB |
testcase_39 | AC | 20 ms
19,924 KB |
testcase_40 | AC | 22 ms
20,052 KB |
testcase_41 | AC | 25 ms
20,308 KB |
testcase_42 | AC | 31 ms
20,820 KB |
testcase_43 | AC | 44 ms
21,676 KB |
testcase_44 | AC | 74 ms
23,660 KB |
testcase_45 | AC | 147 ms
27,372 KB |
testcase_46 | AC | 292 ms
34,796 KB |
testcase_47 | AC | 307 ms
35,048 KB |
testcase_48 | AC | 297 ms
35,048 KB |
testcase_49 | AC | 301 ms
35,176 KB |
testcase_50 | AC | 88 ms
26,992 KB |
testcase_51 | AC | 24 ms
20,308 KB |
testcase_52 | AC | 190 ms
35,248 KB |
testcase_53 | AC | 184 ms
34,488 KB |
testcase_54 | AC | 23 ms
20,180 KB |
testcase_55 | AC | 244 ms
37,992 KB |
testcase_56 | AC | 238 ms
37,992 KB |
testcase_57 | AC | 243 ms
38,248 KB |
testcase_58 | AC | 244 ms
38,120 KB |
testcase_59 | AC | 266 ms
37,992 KB |
testcase_60 | AC | 182 ms
35,304 KB |
testcase_61 | AC | 185 ms
35,816 KB |
testcase_62 | AC | 191 ms
45,032 KB |
testcase_63 | AC | 203 ms
59,880 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; #define rep(i, n) for(int i=0;i<(n);++i) #define rep1(i, n) for(int i=1;i<=(n);i++) #define ll long long using mint = modint; using P = pair<ll,ll>; using lb = long double; #ifdef LOCAL # include <debug_print.hpp> # define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define dbg(...) (static_cast<void>(0)) #endif int n; vector<vector<int>> dp(2e5+5, vector<int>(2)); vector<int> ans(2e5+5); vector<vector<int>> g(2e5+5); int m; struct Edge { int to, cost; Edge(int to, int cost) : to(to), cost(cost) {} }; template <class S, S (*op)(S, S), S (*e)(S)> struct ReRooting { public: ReRooting() : ReRooting(0) {} ReRooting(int n) : ReRooting(std::vector<S>(n)) {} ReRooting(const std::vector<S>& v) : _n(int(v.size())) { dp = std::vector<S>(_n); g = std::vector<vector<Edge>>(_n); ans = std::vector<S>(_n); } void addEdge(int a, int b, int w = 1) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); g[a].push_back(Edge(b, w)); g[b].push_back(Edge(a, w)); } void init(){ dfs1(0); rep(i,_n){ dbg(dp[i].black,dp[i].white); } dfs2(0); } std::vector<S> ans; private: int _n, size, log; std::vector<S> dp; std::vector<vector<Edge>> g; S dfs1(int u, int p=-1){ for(auto [v, cost] : g[u]) { if(v==p) continue; dp[u] = op(dp[u], dfs1(v,u)); } dbg(u,dp[u].white, dp[u].black); return dp[u] = addRoot(dp[u]); } void dfs2(int u, int p = -1){ int N = g[u].size(); if(N==0) return; vector<S> l(N); vector<S> r(N); rep(i,N){ ans[u] = op(ans[u], dp[g[u][i].to]); } ans[u] = addRoot(ans[u]); l[0] = dp[g[u][0].to]; r[N-1] = dp[g[u][N-1].to]; rep(i,N){ int v = g[u][i].to; if(i-1>=0) { l[i] = op(l[i-1],dp[v]); } } for(int i=N-1;i>=0;i--){ int v = g[u][i].to; if(i+1<N) { r[i] = op(r[i+1], dp[v]); } } rep(i,N){ int v = g[u][i].to; if(v==p) continue; dp[u] = {0,0}; if(i-1>=0) { dp[u] = op(dp[u], l[i-1]); } if(i+1<N) { dp[u] = op(dp[u], r[i+1]); } dp[u] = addRoot(dp[u]); dfs2(v, u); } } }; struct S{ int white, black; }; S op(S a, S b) { return S{a.white+b.white, max(a.black,a.white)+max(b.black,b.white)}; } S addRoot(S a) { return S{max(a.black,a.white),a.white+1}; } int main() { cin >> n; if(n==1){ cout<<1<<endl; return 0; } ReRooting<S, op, addRoot> rt(n); rep(i,n-1){ int u, v; cin >> u >> v; --u;--v; rt.addEdge(u,v); } rt.init(); int f = 1e9; rep(i,n){ f = min(f, rt.ans[i].black); } cout<<f<<endl; return 0; }