結果
問題 |
No.2288 Somen Sliders
|
ユーザー |
|
提出日時 | 2023-02-24 00:20:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,428 bytes |
コンパイル時間 | 1,486 ms |
コンパイル使用メモリ | 92,640 KB |
最終ジャッジ日時 | 2025-02-10 20:09:58 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 RE * 2 |
other | AC * 1 WA * 10 RE * 19 |
ソースコード
#include <algorithm> #include <iostream> #include <cassert> #include <queue> using namespace std; typedef long long ll; template <typename T = int> struct edge { int a, b; int preference_a, preference_b; bool is_matched; T cost; int id; bool operator<(const edge<T> &e) const { return preference_a < e.preference_a; } }; template <typename T = int> struct stable_matching { static const int MALE = 0; static const int FEMALE = 1; int p, q, m; std::vector<std::vector<edge<T>>> g; std::vector<std::pair<int, int>> epos; stable_matching() {} stable_matching(int p, int q) : p(p), q(q), m(0) { g.resize(p); } void add_directed_edge(int a, int b, int preference_a, int preference_b, int cost = 1) { assert(0 <= a && a < p); assert(0 <= b && b < q); epos.push_back(std::pair<int, int>(a, (int)g[a].size())); g[a].push_back((edge<T>){a, b, preference_a, preference_b, false, cost, m++}); } void get_stable_matching() { for (int a = 0; a < p; a++) { if (!std::is_sorted(g[a].begin(), g[a].end())) { std::sort(g[a].begin(), g[a].end()); } } std::vector<std::pair<int, int>> mbpos(q, std::pair<int, int>(-1, -1)); std::vector<T> nx(p, 0); std::queue<T> que; for (int a = 0; a < p; a++) { que.push(a); } while (que.size()) { int a = que.front(); que.pop(); for (int &i = nx[a]; i < (int)g[a].size(); i++) { int b = g[a][i].b; int x = mbpos[b].first; if (x >= 0 && g[x][mbpos[b].second].preference_b > g[a][i].preference_b) { g[x][mbpos[b].second].is_matched = false; nx[x]++; que.push(x); x = -1; } if (x == -1) { g[a][i].is_matched = true; mbpos[b] = std::pair<int, int>(a, i); break; } } } } edge<T> &get_edge(int id) { assert(id < m); return g[epos[id].first][epos[id].second]; } }; void solve() { int n, x, y; cin >> n >> x >> y; int p[200005], d[200005]; for (int u = 0; u < n; u++) { p[u] = -1; } int k[200005]; for (int i = 0; i < x; i++) { cin >> k[i]; for (int j = 0; j <= k[i]; j++) { int u; cin >> u; u--; p[u] = i; d[u] = j; } } stable_matching<int> g(y, x); int m = 0; for (int i = 0; i < y; i++) { int k; cin >> k; for (int j = 0; j <= k; j++) { int u; cin >> u; u--; if (p[u] >= 0) { g.add_directed_edge(i, p[u], -j, d[u]); } } } g.get_stable_matching(); int ans = 0; for (int i = 0; i < x; i++) { ans += k[i]; } for (int i = 0; i < g.m; i++) { edge<int> e = g.get_edge(i); if (e.is_matched) { ans -= k[e.b] - e.preference_b; } } cout << ans << endl; } int main() { solve(); }