結果
問題 |
No.1911 Alternately Coloring
|
ユーザー |
|
提出日時 | 2022-04-22 22:09:20 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,925 bytes |
コンパイル時間 | 1,136 ms |
コンパイル使用メモリ | 97,480 KB |
実行使用メモリ | 6,940 KB |
最終ジャッジ日時 | 2024-06-24 03:24:04 |
合計ジャッジ時間 | 6,334 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 WA * 1 |
ソースコード
#include <cstdio> #include <functional> #include <queue> #include <vector> using namespace std; int main() { int N, M; scanf("%d%d", &N, &M); vector<vector<int>> adj(N); for (int i = 0; i < M; i++) { int u, v; scanf("%d%d", &u, &v); adj[u - 1].push_back(v - 1); adj[v - 1].push_back(u - 1); } vector<int> R(N), B(N); for (int &r : R) scanf("%d", &r); for (int &b : B) scanf("%d", &b); vector<bool> vis(N); long ans = 0; auto solve = [&](int a) { long ans = 0, nat = 0; vector<int> target; function<void(int, bool)> dfs = [&](int a, bool b) { vis[a] = true; target.push_back(a); ans += max(R[a], B[a]); nat += b ? R[a] : B[a]; for (auto x : adj[a]) if (!vis[x]) dfs(x, !b); }; dfs(a, true); long sav = min(nat, ans - nat); for (int u : target) { using T = tuple<long, int, bool>; priority_queue<T, vector<T>, greater<T>> Q; Q.emplace(max(R[u], B[u]) - R[u], u, true); vector<bool> vis[2] = {vector<bool>(N), vector<bool>(N)}; while (!Q.empty()) { auto [d, v, t] = Q.top(); Q.pop(); if (vis[t][v]) continue; vis[t][v] = true; if (!t && v == u) { sav = min(sav, d - (max(R[u], B[u]) - min(R[u], B[u]))); break; } for (auto x : adj[v]) Q.emplace(d + max(R[x], B[x]) - (!t ? R[x] : B[x]), x, !t); } } return ans - sav; }; for (int i = 0; i < N; i++) if (!vis[i]) ans = max(ans, solve(i)); printf("%ld\n", ans); }