結果
問題 | No.2677 Minmax Independent Set |
ユーザー | null |
提出日時 | 2024-02-17 20:49:48 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,189 bytes |
コンパイル時間 | 6,363 ms |
コンパイル使用メモリ | 460,220 KB |
実行使用メモリ | 89,336 KB |
最終ジャッジ日時 | 2024-09-30 00:09:14 |
合計ジャッジ時間 | 13,549 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 161 ms
34,372 KB |
testcase_06 | AC | 166 ms
35,180 KB |
testcase_07 | AC | 167 ms
36,016 KB |
testcase_08 | AC | 168 ms
37,616 KB |
testcase_09 | AC | 177 ms
40,592 KB |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 199 ms
89,336 KB |
testcase_13 | AC | 192 ms
50,636 KB |
testcase_14 | AC | 180 ms
51,244 KB |
testcase_15 | AC | 209 ms
63,324 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | AC | 118 ms
32,396 KB |
testcase_29 | AC | 200 ms
66,432 KB |
testcase_30 | AC | 2 ms
6,816 KB |
testcase_31 | AC | 2 ms
6,816 KB |
testcase_32 | AC | 2 ms
6,820 KB |
testcase_33 | WA | - |
testcase_34 | AC | 2 ms
6,820 KB |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | WA | - |
testcase_45 | WA | - |
testcase_46 | WA | - |
testcase_47 | WA | - |
testcase_48 | WA | - |
testcase_49 | WA | - |
testcase_50 | AC | 41 ms
14,332 KB |
testcase_51 | AC | 4 ms
6,816 KB |
testcase_52 | AC | 95 ms
27,196 KB |
testcase_53 | AC | 97 ms
25,468 KB |
testcase_54 | AC | 4 ms
6,816 KB |
testcase_55 | WA | - |
testcase_56 | WA | - |
testcase_57 | WA | - |
testcase_58 | WA | - |
testcase_59 | WA | - |
testcase_60 | AC | 85 ms
27,812 KB |
testcase_61 | WA | - |
testcase_62 | AC | 97 ms
41,132 KB |
testcase_63 | AC | 115 ms
61,288 KB |
ソースコード
/*このコード、と~おれ!Be accepted!∧_∧(。・ω・。)つ━☆・*。⊂ ノ ・゜+.しーJ °。+ *´¨).· ´¸.·*´¨) ¸.·*¨)(¸.·´ (¸.·'* ☆*/#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <vector>#include <numeric>#include <iostream>#include <random>#include <map>#include <unordered_map>#include <queue>#include <regex>#include <functional>#include <complex>#include <list>#include <cassert>#include <iomanip>#include <set>#include <stack>#include <bitset>#include <array>#include <chrono>#include <unordered_set>//#pragma GCC target("arch=skylake-avx512")//#pragma GCC target("avx2")//#pragma GCC optimize("O3")//#pragma GCC optimize("Ofast")//#pragma GCC target("sse4")//#pragma GCC optimize("unroll-loops")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#define repeat(i, n, m) for(int i = n; i < (m); ++i)#define rep(i, n) for(int i = 0; i < (n); ++i)#define printynl(a) printf(a ? "yes\n" : "no\n")#define printyn(a) printf(a ? "Yes\n" : "No\n")#define printYN(a) printf(a ? "YES\n" : "NO\n")#define printim(a) printf(a ? "possible\n" : "imposible\n")#define printdb(a) printf("%.50lf\n", a)#define printLdb(a) printf("%.50Lf\n", a)#define printdbd(a) printf("%.16lf\n", a)#define prints(s) printf("%s\n", s.c_str())#define all(x) (x).begin(), (x).end()#define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI)#define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L)#define Please return#define AC 0#define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d))using ll = long long;using ull = unsigned long long;constexpr int INF = 1073741823;constexpr int MINF = -1073741823;constexpr ll LINF = ll(4661686018427387903);constexpr ll MOD = 1e9 + 7;constexpr ll mod = 998244353;constexpr long double eps = 1e-14;const long double PI = acosl(-1.0L);using namespace std;void scans(string& str) {char c;str = "";scanf("%c", &c);if (c == '\n')scanf("%c", &c);while (c != '\n' && c != -1 && c != ' ') {str += c;scanf("%c", &c);}}void scanc(char& str) {char c;scanf("%c", &c);if (c == -1)return;while (c == '\n') {scanf("%c", &c);}str = c;}double acot(double x) {return PI / 2 - atan(x);}ll LSB(ll n) { return (n & (-n)); }template<typename T>inline T chmin(T& a, const T& b) {if (a > b)a = b;return a;}template<typename T>inline T chmax(T& a, const T& b) {if (a < b)a = b;return a;}//cpp_int#if __has_include(<boost/multiprecision/cpp_int.hpp>)#include <boost/multiprecision/cpp_int.hpp>#include <boost/multiprecision/cpp_dec_float.hpp>using namespace boost::multiprecision;#elseusing cpp_int = ll;#endif//atcoder library#if __has_include(<atcoder/all>)#include <atcoder/all>//using namespace atcoder;#endif/*random_device seed_gen;mt19937 engine(seed_gen());uniform_int_distribution dist(1, 100);*//*----------------------------------------------------------------------------------*//* Rerooting: 全方位木 DP問題ごとに以下を書き換える- 型DPと単位元- 型DPに対する二項演算 merge- まとめたDPを用いて新たな部分木のDPを計算する add_root計算量: O(N)*/struct Rerooting {/* start 問題ごとに書き換え */struct DP { // DP の型int dp0, dp1;DP(int dp0_, int dp1_) : dp0(dp0_), dp1(dp1_) {}};const DP identity = DP(0, 0); // 単位元(末端の値は add_root(identity) になるので注意)function<DP(DP, DP)> merge = [](DP dp_cum, DP d) -> DP {return DP(dp_cum.dp0 + d.dp0, dp_cum.dp1 + d.dp1);};function<DP(DP)> add_root = [](DP d) -> DP {return DP(max(d.dp0, d.dp1), d.dp0 + 1);};/* end 問題ごとに書き換え */// グラフの定義struct Edge {int to;};using Graph = vector<vector<Edge>>;vector<vector<DP>> dp; // dp[v][i]: vから出るi番目の有向辺に対応する部分木のDPvector<DP> ans; // ans[v]: 頂点vを根とする木の答えGraph G;Rerooting(int N) : G(N) {dp.resize(N);ans.assign(N, identity);}void add_edge(int a, int b) {G[a].push_back({ b });}void build() {dfs(0); // 普通に木DPbfs(0, identity); // 残りの部分木に対応するDPを計算}DP dfs(int v, int p = -1) { // 頂点v, 親pDP dp_cum = identity;int deg = G[v].size();dp[v] = vector<DP>(deg, identity);for (int i = 0; i < deg; i++) {int u = G[v][i].to;if (u == p) continue;dp[v][i] = dfs(u, v);dp_cum = merge(dp_cum, dp[v][i]);}return add_root(dp_cum);}void bfs(int v, const DP& dp_p, int p = -1) { // bfs だが、実装が楽なので中身は dfs になっているint deg = G[v].size();for (int i = 0; i < deg; i++) { // 前のbfsで計算した有向辺に対応する部分木のDPを保存if (G[v][i].to == p) dp[v][i] = dp_p;}vector<DP> dp_l(deg + 1, identity), dp_r(deg + 1, identity); // 累積mergefor (int i = 0; i < deg; i++) {dp_l[i + 1] = merge(dp_l[i], dp[v][i]);}for (int i = deg - 1; i >= 0; i--) {dp_r[i] = merge(dp_r[i + 1], dp[v][i]);}ans[v] = add_root(dp_l[deg]); // 頂点 v の答えfor (int i = 0; i < deg; i++) { // 一つ隣の頂点に対しても同様に計算int u = G[v][i].to;if (u == p) continue;bfs(u, add_root(merge(dp_l[i], dp_r[i + 1])), v);}}};int main() {int n;scanf("%d", &n);Rerooting reroot(n);rep(i, n - 1) {int a, b;scanf("%d %d", &a, &b);a--, b--;reroot.add_edge(a, b);reroot.add_edge(b, a);}reroot.build();int ans = INF;rep(i, n) {chmin(ans, reroot.ans[i].dp1);}printf("%d\n", ans);Please AC;}