結果
問題 | No.912 赤黒木 |
ユーザー | 👑 emthrm |
提出日時 | 2019-10-19 02:02:24 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 261 ms / 3,000 ms |
コード長 | 3,074 bytes |
コンパイル時間 | 1,386 ms |
コンパイル使用メモリ | 126,716 KB |
実行使用メモリ | 41,504 KB |
最終ジャッジ日時 | 2023-09-08 07:06:00 |
合計ジャッジ時間 | 8,827 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
11,052 KB |
testcase_01 | AC | 5 ms
11,224 KB |
testcase_02 | AC | 5 ms
11,320 KB |
testcase_03 | AC | 6 ms
11,264 KB |
testcase_04 | AC | 5 ms
11,096 KB |
testcase_05 | AC | 6 ms
11,236 KB |
testcase_06 | AC | 5 ms
11,148 KB |
testcase_07 | AC | 6 ms
11,164 KB |
testcase_08 | AC | 5 ms
11,164 KB |
testcase_09 | AC | 6 ms
11,116 KB |
testcase_10 | AC | 6 ms
11,172 KB |
testcase_11 | AC | 6 ms
11,100 KB |
testcase_12 | AC | 187 ms
17,412 KB |
testcase_13 | AC | 194 ms
17,572 KB |
testcase_14 | AC | 185 ms
17,172 KB |
testcase_15 | AC | 207 ms
17,700 KB |
testcase_16 | AC | 192 ms
17,480 KB |
testcase_17 | AC | 200 ms
17,404 KB |
testcase_18 | AC | 188 ms
17,504 KB |
testcase_19 | AC | 197 ms
17,224 KB |
testcase_20 | AC | 196 ms
17,068 KB |
testcase_21 | AC | 190 ms
17,128 KB |
testcase_22 | AC | 134 ms
19,476 KB |
testcase_23 | AC | 135 ms
19,620 KB |
testcase_24 | AC | 135 ms
19,564 KB |
testcase_25 | AC | 203 ms
17,396 KB |
testcase_26 | AC | 210 ms
17,684 KB |
testcase_27 | AC | 211 ms
17,348 KB |
testcase_28 | AC | 257 ms
41,504 KB |
testcase_29 | AC | 243 ms
41,380 KB |
testcase_30 | AC | 261 ms
41,484 KB |
testcase_31 | AC | 239 ms
39,724 KB |
ソースコード
#include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <chrono> #define _USE_MATH_DEFINES #include <cmath> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <iomanip> #include <iterator> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <tuple> #include <utility> #include <vector> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() const int INF = 0x3f3f3f3f; const long long LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; struct IOSetup { IOSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); cerr << fixed << setprecision(10); } } iosetup; /*-------------------------------------------------*/ vector<int> graph[200000]; int subtree[200000] = {}, dp[200000][3] = {}; bool odd[200000] = {}; void dfs1(int par, int ver) { if (odd[ver]) subtree[ver] = 1; for (int e : graph[ver]) if (e != par) { dfs1(ver, e); subtree[ver] += subtree[e]; } } void dfs2(int par, int ver) { for (int e : graph[ver]) { if (e != par) dfs2(ver, e); } dp[ver][0] = 0; for (int e : graph[ver]) if (e != par) { dp[ver][0] += dp[e][0]; if (subtree[e] & 1) ++dp[ver][0]; } if (subtree[ver] >= 1) { int mn = INF; for (int e : graph[ver]) if (e != par) { int zero = dp[e][0] + (subtree[e] & 1); int one = dp[e][1] + (subtree[e] % 2 == 0); mn = min(mn, one - zero); } dp[ver][1] = min(dp[ver][1], dp[ver][0] + mn); if (odd[ver]) dp[ver][1] = min(dp[ver][1], dp[ver][0]); if (subtree[ver] >= 2) { int mn2 = INF; for (int e : graph[ver]) if (e != par) { int zero = dp[e][0] + (subtree[e] & 1); int two = dp[e][2] + (subtree[e] & 1); mn2 = min(mn2, two - zero); } dp[ver][2] = min(dp[ver][2], dp[ver][0] + mn2); vector<int> mn1; for (int e : graph[ver]) if (e != par) { int zero = dp[e][0] + (subtree[e] & 1); int one = dp[e][1] + (subtree[e] % 2 == 0); mn1.emplace_back(one - zero); } if (mn1.size() >= 2) { sort(ALL(mn1)); int mnmn = mn1[0] + mn1[1]; dp[ver][2] = min(dp[ver][2], dp[ver][0] + mnmn); } if (odd[ver]) dp[ver][2] = min(dp[ver][2], dp[ver][0] + mn); } } } int main() { memset(dp, INF, sizeof(dp)); int n; cin >> n; REP(_, n - 1) { int a, b; cin >> a >> b; --a; --b; graph[a].emplace_back(b); graph[b].emplace_back(a); } REP(_, n - 1) { int c, d; cin >> c >> d; --c; --d; odd[c] = !odd[c]; odd[d] = !odd[d]; } dfs1(-1, 0); dfs2(-1, 0); cout << n - 1 + min(dp[0][0], dp[0][2]) << '\n'; return 0; }