結果
問題 | No.1775 Love Triangle 2 |
ユーザー | hitonanode |
提出日時 | 2021-11-24 23:00:04 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,116 bytes |
コンパイル時間 | 2,003 ms |
コンパイル使用メモリ | 122,044 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-03 21:11:53 |
合計ジャッジ時間 | 4,371 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 21 ms
6,944 KB |
testcase_05 | AC | 21 ms
6,940 KB |
testcase_06 | AC | 22 ms
6,944 KB |
testcase_07 | AC | 10 ms
6,940 KB |
testcase_08 | AC | 26 ms
6,944 KB |
testcase_09 | AC | 3 ms
6,940 KB |
testcase_10 | AC | 4 ms
6,940 KB |
testcase_11 | AC | 3 ms
6,940 KB |
testcase_12 | AC | 4 ms
6,944 KB |
testcase_13 | AC | 4 ms
6,940 KB |
testcase_14 | AC | 5 ms
6,944 KB |
testcase_15 | AC | 8 ms
6,944 KB |
testcase_16 | AC | 9 ms
6,940 KB |
testcase_17 | AC | 11 ms
6,940 KB |
testcase_18 | AC | 18 ms
6,944 KB |
testcase_19 | AC | 4 ms
6,940 KB |
testcase_20 | AC | 3 ms
6,944 KB |
testcase_21 | AC | 4 ms
6,940 KB |
testcase_22 | AC | 3 ms
6,940 KB |
testcase_23 | AC | 4 ms
6,944 KB |
testcase_24 | AC | 3 ms
6,944 KB |
testcase_25 | AC | 4 ms
6,940 KB |
testcase_26 | AC | 4 ms
6,940 KB |
testcase_27 | AC | 4 ms
6,944 KB |
testcase_28 | AC | 5 ms
6,944 KB |
testcase_29 | AC | 21 ms
6,940 KB |
testcase_30 | AC | 23 ms
6,944 KB |
testcase_31 | AC | 15 ms
6,940 KB |
testcase_32 | AC | 13 ms
6,944 KB |
testcase_33 | AC | 9 ms
6,944 KB |
testcase_34 | AC | 10 ms
6,940 KB |
testcase_35 | AC | 7 ms
6,944 KB |
testcase_36 | AC | 4 ms
6,940 KB |
testcase_37 | AC | 3 ms
6,944 KB |
testcase_38 | AC | 3 ms
6,944 KB |
testcase_39 | AC | 23 ms
6,944 KB |
testcase_40 | AC | 17 ms
6,940 KB |
testcase_41 | AC | 12 ms
6,944 KB |
testcase_42 | AC | 13 ms
6,940 KB |
testcase_43 | AC | 9 ms
6,940 KB |
testcase_44 | AC | 10 ms
6,940 KB |
testcase_45 | AC | 7 ms
6,940 KB |
testcase_46 | AC | 5 ms
6,944 KB |
testcase_47 | AC | 3 ms
6,944 KB |
testcase_48 | AC | 3 ms
6,944 KB |
testcase_49 | AC | 18 ms
6,940 KB |
testcase_50 | AC | 24 ms
6,940 KB |
testcase_51 | AC | 15 ms
6,944 KB |
testcase_52 | AC | 14 ms
6,944 KB |
testcase_53 | AC | 9 ms
6,940 KB |
testcase_54 | AC | 10 ms
6,940 KB |
testcase_55 | AC | 7 ms
6,940 KB |
testcase_56 | AC | 4 ms
6,940 KB |
testcase_57 | AC | 4 ms
6,944 KB |
testcase_58 | AC | 4 ms
6,940 KB |
testcase_59 | AC | 23 ms
6,940 KB |
testcase_60 | AC | 16 ms
6,940 KB |
testcase_61 | AC | 13 ms
6,940 KB |
testcase_62 | AC | 12 ms
6,944 KB |
testcase_63 | AC | 9 ms
6,944 KB |
testcase_64 | AC | 7 ms
6,944 KB |
testcase_65 | AC | 5 ms
6,940 KB |
testcase_66 | AC | 4 ms
6,944 KB |
testcase_67 | AC | 4 ms
6,940 KB |
testcase_68 | AC | 3 ms
6,944 KB |
testcase_69 | WA | - |
testcase_70 | WA | - |
testcase_71 | WA | - |
testcase_72 | WA | - |
testcase_73 | WA | - |
testcase_74 | WA | - |
testcase_75 | WA | - |
testcase_76 | WA | - |
testcase_77 | WA | - |
testcase_78 | WA | - |
testcase_79 | WA | - |
testcase_80 | WA | - |
testcase_81 | WA | - |
testcase_82 | WA | - |
testcase_83 | WA | - |
testcase_84 | WA | - |
testcase_85 | WA | - |
testcase_86 | WA | - |
testcase_87 | WA | - |
testcase_88 | WA | - |
testcase_89 | AC | 3 ms
6,944 KB |
ソースコード
// 各辺にコスト1を割り当て,x->y, x->z に流量 2 の最小費用流を流し,x->y のパスを固定して // 残りの頂点と辺で z->x, z->y に流量 2 の最小費用流を流す #include <algorithm> #include <iostream> #include <utility> #include <vector> using namespace std; #include <cassert> #include <tuple> namespace INPUT { using namespace std; tuple<int, int, int, int, vector<vector<int>>> read() { int N, M, X, Y, Z; cin >> N >> M >> X >> Y >> Z; --X, --Y, --Z; vector mat(N, vector<int>(N)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { mat[i][j] = (i != j); } } while (M--) { int a, b; cin >> a >> b; --a, --b; mat[a][b] = mat[b][a] = 0; } vector<vector<int>> to(N); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (mat[i][j]) to[i].push_back(j); } } return {N, X, Y, Z, to}; } }; // namespace INPUT #line 3 "twopaths.hpp" #include <atcoder/mincostflow> #line 8 "twopaths.hpp" // 各辺にコスト1を割り当て,x->y, x->z に流量 2 の最小費用流を流し,x->y のパスを固定して // 残りの頂点と辺で z->x, z->y に流量 2 の最小費用流を流す namespace TWOPATHS { using namespace std; // used_vs に含まれる頂点は使わずに,from -> to1 と from->to2 の点素なパスを構成する. // 両方のパスが構築できなければ empty vector の組を返す. pair<vector<int>, vector<int>> twopaths(const vector<vector<int>> &to, const vector<int> &used_vs, int from, int to1, int to2) { const int N = to.size(); const int gt = N * 2; atcoder::mcf_graph<int, int> graph(gt + 1); vector<int> valid_v(N, 1); for (auto i : used_vs) valid_v[i] = 0; valid_v[to1] = valid_v[to2] = 0; for (int i = 0; i < N; ++i) { graph.add_edge(i, i + N, valid_v[i], 0); } graph.add_edge(to1, to1 + N, 1, 0); graph.add_edge(to2, to2 + N, 1, 0); for (int i = 0; i < N; ++i) { for (auto j : to[i]) { int cost = 1; graph.add_edge(i + N, j, 1, cost); } } graph.add_edge(to1 + N, gt, 1, 0); graph.add_edge(to2 + N, gt, 1, 0); auto f = graph.flow(from + N, gt, 2); if (f.first < 2) return {{}, {}}; vector<vector<int>> conn(N); for (auto e : graph.edges()) { if (e.flow) { if (e.to == gt) continue; int s = e.from % N, t = e.to % N; if (s != t) conn[s].push_back(t); } } vector<vector<int>> ret; while (conn[from].size()) { int now = from; vector<int> vec{now}; while (conn[now].size()) { int nxt = conn[now].back(); conn[now].pop_back(); now = nxt; vec.push_back(now); } ret.push_back(vec); } assert(ret.size() == 2); if (ret[0].back() != to1) swap(ret[0], ret[1]); if (ret[1].back() != to2) swap(ret[0], ret[1]); return {ret.at(0), ret.at(1)}; } constexpr int inf = 1 << 20; int solve_fake_flow_sub(const vector<vector<int>> &to, const vector<int> &banxy, int z, int x, int y) { auto [p1, p2] = twopaths(to, banxy, z, x, y); if (p1.empty()) return inf; return p1.size() + p2.size() + banxy.size() - 1; } int solve_by_flow_twice(const vector<vector<int>> &to, int x, int y, int z) { int N = to.size(); vector<int> vs{x, y, z}; sort(vs.begin(), vs.end()); int ret = inf; do { auto [p01, p02] = twopaths(to, {}, vs[0], vs[1], vs[2]); if (p01.empty() or p02.empty()) continue; auto ban01 = p01, ban02 = p02; for (int t = 0; t < 2; ++t) { ban01.pop_back(), ban02.pop_back(); reverse(ban01.begin(), ban01.end()), reverse(ban02.begin(), ban02.end()); } ret = min(ret, solve_fake_flow_sub(to, ban01, vs[2], vs[0], vs[1])); ret = min(ret, solve_fake_flow_sub(to, ban02, vs[1], vs[0], vs[2])); } while (next_permutation(vs.begin(), vs.end())); for (int u = 0; u < 3; ++u) { auto [p01a, p01b] = twopaths(to, {}, vs[0], vs[1], vs[1]); if (p01a.empty()) continue; if (count(p01a.begin(), p01a.end(), vs[2]) or count(p01b.begin(), p01b.end(), vs[2])) { ret = min<int>(ret, p01a.size() + p01b.size() - 2); } else { auto ban01a = p01a, ban01b = p01b; for (int t = 0; t < 2; ++t) { ban01a.pop_back(), ban01b.pop_back(); reverse(ban01a.begin(), ban01a.end()), reverse(ban01b.begin(), ban01b.end()); } ret = min(ret, solve_fake_flow_sub(to, ban01a, vs[2], vs[0], vs[1])); ret = min(ret, solve_fake_flow_sub(to, ban01b, vs[2], vs[0], vs[1])); } rotate(vs.begin(), vs.begin() + 1, vs.end()); } return ret <= N ? ret : -1; } } #line 11 "uso_determin.cpp" int main() { cin.tie(nullptr), ios::sync_with_stdio(false); auto [N, X, Y, Z, to] = INPUT::read(); int ret = TWOPATHS::solve_by_flow_twice(to, X, Y, Z); cout << ret << '\n'; }