結果
問題 | No.1984 [Cherry 4th Tune *] Dilemma |
ユーザー |
|
提出日時 | 2022-06-17 22:51:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 5,744 bytes |
コンパイル時間 | 2,712 ms |
コンパイル使用メモリ | 212,812 KB |
最終ジャッジ日時 | 2025-01-29 22:31:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 68 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < n; i++)#define rep2(i, x, n) for (int i = x; i <= n; i++)#define rep3(i, x, n) for (int i = x; i >= n; i--)#define each(e, v) for (auto &e : v)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;template <typename T>bool chmax(T &x, const T &y) {return (x < y) ? (x = y, true) : false;}template <typename T>bool chmin(T &x, const T &y) {return (x > y) ? (x = y, true) : false;}template <typename T>int flg(T x, int i) {return (x >> i) & 1;}template <typename T>void print(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');if (v.empty()) cout << '\n';}template <typename T>void printn(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << '\n';}template <typename T>int lb(const vector<T> &v, T x) {return lower_bound(begin(v), end(v), x) - begin(v);}template <typename T>int ub(const vector<T> &v, T x) {return upper_bound(begin(v), end(v), x) - begin(v);}template <typename T>void rearrange(vector<T> &v) {sort(begin(v), end(v));v.erase(unique(begin(v), end(v)), end(v));}template <typename T>vector<int> id_sort(const vector<T> &v, bool greater = false) {int n = v.size();vector<int> ret(n);iota(begin(ret), end(ret), 0);sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; });return ret;}template <typename S, typename T>pair<S, T> operator+(const pair<S, T> &p, const pair<S, T> &q) {return make_pair(p.first + q.first, p.second + q.second);}template <typename S, typename T>pair<S, T> operator-(const pair<S, T> &p, const pair<S, T> &q) {return make_pair(p.first - q.first, p.second - q.second);}template <typename S, typename T>istream &operator>>(istream &is, pair<S, T> &p) {S a;T b;is >> a >> b;p = make_pair(a, b);return is;}template <typename S, typename T>ostream &operator<<(ostream &os, const pair<S, T> &p) {return os << p.first << ' ' << p.second;}struct io_setup {io_setup() {ios_base::sync_with_stdio(false);cin.tie(NULL);cout << fixed << setprecision(15);}} io_setup;const int inf = (1 << 30) - 1;const ll INF = (1LL << 50) - 1;const int MOD = 1000000007;// const int MOD = 998244353;template <typename F> // 流量の型struct Dinic {struct edge {int to;F cap;int rev;edge(int to, F cap, int rev) : to(to), cap(cap), rev(rev) {}};vector<vector<edge>> es;vector<int> d, pos;const F INF_F = numeric_limits<F>::max() / 2;const int n;Dinic(int n) : es(n), d(n), pos(n), n(n) {}void add_edge(int from, int to, F cap, bool directed = true) {es[from].emplace_back(to, cap, (int)es[to].size());es[to].emplace_back(from, directed ? 0 : cap, (int)es[from].size() - 1);}bool _bfs(int s, int t) {fill(begin(d), end(d), -1);queue<int> que;d[s] = 0;que.push(s);while (!que.empty()) {int i = que.front();que.pop();for (auto &e : es[i]) {if (e.cap > 0 && d[e.to] == -1) {d[e.to] = d[i] + 1;que.push(e.to);}}}return d[t] != -1;}F _dfs(int now, int t, F flow) {if (now == t) return flow;for (int &i = pos[now]; i < (int)es[now].size(); i++) {edge &e = es[now][i];if (e.cap > 0 && d[e.to] > d[now]) {F f = _dfs(e.to, t, min(flow, e.cap));if (f > 0) {e.cap -= f;es[e.to][e.rev].cap += f;return f;}}}return 0;}F max_flow(int s, int t) { // 操作後の d 配列は最小カットの 1 つを表す(0 以上なら s 側、-1 なら t 側)F flow = 0;while (_bfs(s, t)) {fill(begin(pos), end(pos), 0);F f = 0;while ((f = _dfs(s, t, INF_F)) > 0) flow += f;}return flow;}};int main() {int N, M, K, P;cin >> N >> M >> K >> P;Dinic<ll> G(N + M + K + 2);int s = N + M + K, t = s + 1;ll ans = 0;rep(i, N) {ll E;cin >> E;ans += E;G.add_edge(s, i, E);}rep(i, M) {ll F;cin >> F;ans += F;G.add_edge(N + i, t, F);}rep(i, K) {ll V;cin >> V;G.add_edge(N + M + i, t, V);}rep(i, N) {int L;cin >> L;while (L--) {int A;cin >> A;A--;G.add_edge(i, N + M + A, INF);}}rep(i, P) {int I, J;cin >> I >> J;I--, J--;G.add_edge(I, N + J, INF);}cout << ans - G.max_flow(s, t) << '\n';vector<pii> ret;vector<string> S = {"Goal", "Action", "Preparation"};rep(i, K) {if (G.d[N + M + i] >= 0) ret.eb(2, i);}rep(i, M) {if (G.d[N + i] < 0) ret.eb(1, i);}rep(i, N) {if (G.d[i] >= 0) ret.eb(0, i);}cout << sz(ret) << '\n';each(e, ret) {auto [i, j] = e;cout << S[i] << ' ' << j + 1 << '\n';}}