結果
問題 | No.1911 Alternately Coloring |
ユーザー |
|
提出日時 | 2022-04-22 22:12:01 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 244 ms / 4,000 ms |
コード長 | 1,964 bytes |
コンパイル時間 | 1,403 ms |
コンパイル使用メモリ | 98,260 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-24 03:27:07 |
合計ジャッジ時間 | 6,409 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 29 |
ソースコード
#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, n1 = 0, n2 = 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]); n1 += b ? R[a] : B[a]; n2 += b ? B[a] : R[a]; for (auto x : adj[a]) if (!vis[x]) dfs(x, !b); }; dfs(a, true); long sav = ans - max(n1, n2); 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); }