結果
問題 | No.2677 Minmax Independent Set |
ユーザー | 2qbingxuan |
提出日時 | 2024-03-15 23:19:28 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 137 ms / 2,000 ms |
コード長 | 4,606 bytes |
コンパイル時間 | 2,830 ms |
コンパイル使用メモリ | 254,220 KB |
実行使用メモリ | 37,564 KB |
最終ジャッジ日時 | 2024-09-30 02:53:30 |
合計ジャッジ時間 | 7,727 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 93 ms
18,048 KB |
testcase_06 | AC | 80 ms
18,176 KB |
testcase_07 | AC | 85 ms
18,384 KB |
testcase_08 | AC | 91 ms
18,892 KB |
testcase_09 | AC | 84 ms
19,968 KB |
testcase_10 | AC | 67 ms
16,504 KB |
testcase_11 | AC | 63 ms
16,380 KB |
testcase_12 | AC | 104 ms
37,564 KB |
testcase_13 | AC | 95 ms
23,540 KB |
testcase_14 | AC | 89 ms
23,512 KB |
testcase_15 | AC | 98 ms
28,044 KB |
testcase_16 | AC | 91 ms
15,988 KB |
testcase_17 | AC | 87 ms
15,888 KB |
testcase_18 | AC | 53 ms
11,336 KB |
testcase_19 | AC | 64 ms
12,780 KB |
testcase_20 | AC | 22 ms
6,816 KB |
testcase_21 | AC | 72 ms
13,836 KB |
testcase_22 | AC | 6 ms
6,816 KB |
testcase_23 | AC | 2 ms
6,816 KB |
testcase_24 | AC | 2 ms
6,816 KB |
testcase_25 | AC | 2 ms
6,820 KB |
testcase_26 | AC | 1 ms
6,816 KB |
testcase_27 | AC | 2 ms
6,816 KB |
testcase_28 | AC | 62 ms
16,568 KB |
testcase_29 | AC | 137 ms
29,428 KB |
testcase_30 | AC | 2 ms
6,816 KB |
testcase_31 | AC | 2 ms
6,820 KB |
testcase_32 | AC | 2 ms
6,816 KB |
testcase_33 | AC | 2 ms
6,816 KB |
testcase_34 | AC | 1 ms
6,820 KB |
testcase_35 | AC | 2 ms
6,816 KB |
testcase_36 | AC | 2 ms
6,820 KB |
testcase_37 | AC | 2 ms
6,816 KB |
testcase_38 | AC | 2 ms
6,816 KB |
testcase_39 | AC | 2 ms
6,816 KB |
testcase_40 | AC | 3 ms
6,820 KB |
testcase_41 | AC | 3 ms
6,820 KB |
testcase_42 | AC | 5 ms
6,816 KB |
testcase_43 | AC | 10 ms
6,816 KB |
testcase_44 | AC | 20 ms
6,820 KB |
testcase_45 | AC | 39 ms
9,472 KB |
testcase_46 | AC | 88 ms
15,828 KB |
testcase_47 | AC | 88 ms
15,896 KB |
testcase_48 | AC | 90 ms
15,832 KB |
testcase_49 | AC | 88 ms
15,800 KB |
testcase_50 | AC | 23 ms
8,152 KB |
testcase_51 | AC | 3 ms
6,816 KB |
testcase_52 | AC | 52 ms
14,232 KB |
testcase_53 | AC | 47 ms
13,288 KB |
testcase_54 | AC | 3 ms
6,816 KB |
testcase_55 | AC | 72 ms
16,552 KB |
testcase_56 | AC | 68 ms
16,488 KB |
testcase_57 | AC | 69 ms
16,588 KB |
testcase_58 | AC | 67 ms
16,560 KB |
testcase_59 | AC | 65 ms
16,560 KB |
testcase_60 | AC | 55 ms
15,872 KB |
testcase_61 | AC | 57 ms
16,024 KB |
testcase_62 | AC | 69 ms
20,124 KB |
testcase_63 | AC | 66 ms
27,204 KB |
ソースコード
// An AC a day keeps the doctor away. #include <bits/stdc++.h> using namespace std; /*{{{*/ #define all(x) begin(x), end(x) #ifdef CKISEKI #include <experimental/iterator> #define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n" #define debug(a...) debug_(#a, a) #define orange(a...) orange_(#a, a) void debug_(auto s, auto ...a) { cerr << "\e[1;32m(" << s << ") = ("; int f = 0; (..., (cerr << (f++ ? ", " : "") << a)); cerr << ")\e[0m\n"; } void orange_(auto s, auto L, auto R) { cerr << "\e[1;33m[ " << s << " ] = [ "; using namespace experimental; copy(L, R, make_ostream_joiner(cerr, ", ")); cerr << " ]\e[0m\n"; } #else #define safe ((void)0) #define debug(...) safe #define orange(...) safe #endif template <typename T, T MOD> class Modular { public: constexpr Modular() : v() {} template <typename U> Modular(const U &u) { v = (0 <= u && u < MOD ? u : (u%MOD+MOD)%MOD); } template <typename U> explicit operator U() const { return U(v); } T operator()() const { return v; } #define REFOP(type, expr...) Modular &operator type (const Modular &rhs) { return expr, *this; } REFOP(+=, v += rhs.v - MOD, v += MOD & (v >> width)) ; REFOP(-=, v -= rhs.v, v += MOD & (v >> width)) // fits for MOD^2 <= 9e18 REFOP(*=, v = static_cast<T>(1LL * v * rhs.v % MOD)) ; REFOP(/=, *this *= inverse(rhs.v)) #define VALOP(op) friend Modular operator op (Modular a, const Modular &b) { return a op##= b; } VALOP(+) ; VALOP(-) ; VALOP(*) ; VALOP(/) Modular operator-() const { return 0 - *this; } friend bool operator == (const Modular &lhs, const Modular &rhs) { return lhs.v == rhs.v; } friend bool operator != (const Modular &lhs, const Modular &rhs) { return lhs.v != rhs.v; } friend std::istream & operator>>(std::istream &I, Modular &m) { T x; I >> x, m = x; return I; } friend std::ostream & operator<<(std::ostream &O, const Modular &m) { return O << m.v; } private: constexpr static int width = sizeof(T) * 8 - 1; T v; static T inverse(T a) { // copy from tourist's template T u = 0, v = 1, m = MOD; while (a != 0) { T t = m / a; m -= t * a; std::swap(a, m); u -= t * v; std::swap(u, v); } assert(m == 1); return u; } }; using lld = int64_t; using llf = long double; template <typename T> using max_heap = std::priority_queue<T,vector<T>,less<T> >; template <typename T> using min_heap = std::priority_queue<T,vector<T>,greater<T> >; template <typename V, typename T> int get_pos(const V &v, T x) { return lower_bound(all(v),x) - begin(v); } template <typename V> void sort_uni(V &v) { sort(all(v)), v.erase(unique(all(v)),end(v)); } template <typename T> bool chmin(T &x, const T &v) { return v < x ? (x=v, true) : false; } template <typename T> bool chmax(T &x, const T &v) { return x < v ? (x=v, true) : false; } constexpr inline lld cdiv(lld x, lld m) { return x/m + (x%m ? (x<0) ^ (m>0) : 0); } // ceiling divide constexpr inline lld modpow(lld e,lld p,lld m) { lld r=1; for(e%=m;p;p>>=1,e=e*e%m) if(p&1) r=r*e%m; return r; }/*}}}*/ constexpr llf eps = 1e-9; constexpr lld maxn = 200025, INF = 1e18, mod = 998244353, K = 14699, inf = 1e9; using Mint = Modular<int, mod>; Mint modpow(Mint e, uint64_t p) { Mint r = 1; while (p) (p&1) && (r *= e), e *= e, p >>= 1; return r; } // 0^0 = 1 const auto dummy = [] { return cin.tie(nullptr)->sync_with_stdio(false); }(); signed main() { int N; cin >> N; vector<vector<int>> g(N); for (int i = 1; i < N; i++) { int u, v; cin >> u >> v; --u, --v; g[u].emplace_back(v); g[v].emplace_back(u); } vector<array<int, 2>> dp(N); auto dfs = [&](auto self, int i, int f) -> void { dp[i][1] = 1; for (int j : g[i]) if (j != f) { self(self, j, i); const auto &s = dp[j]; dp[i][0] += max(s[0], s[1]); dp[i][1] += s[0]; } }; dfs(dfs, 0, -1); int ans = inf; auto reroot = [&](auto self, int i, int f) -> void { ans = min(ans, dp[i][1]); debug(i+1, dp[i][1]); for (int j : g[i]) if (j != f) { { const auto &s = dp[j]; dp[i][0] -= max(s[0], s[1]); dp[i][1] -= s[0]; } { const auto &s = dp[i]; dp[j][0] += max(s[0], s[1]); dp[j][1] += s[0]; } self(self, j, i); { const auto &s = dp[i]; dp[j][0] -= max(s[0], s[1]); dp[j][1] -= s[0]; } { const auto &s = dp[j]; dp[i][0] += max(s[0], s[1]); dp[i][1] += s[0]; } } }; reroot(reroot, 0, -1); cout << ans << '\n'; }