結果
問題 | No.1984 [Cherry 4th Tune *] Dilemma |
ユーザー | cologne |
提出日時 | 2022-03-24 11:34:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 6,399 bytes |
コンパイル時間 | 1,734 ms |
コンパイル使用メモリ | 99,080 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-08 13:57:10 |
合計ジャッジ時間 | 7,634 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 3 ms
5,248 KB |
testcase_23 | AC | 3 ms
5,248 KB |
testcase_24 | AC | 3 ms
5,248 KB |
testcase_25 | AC | 3 ms
5,248 KB |
testcase_26 | AC | 3 ms
5,248 KB |
testcase_27 | AC | 3 ms
5,248 KB |
testcase_28 | AC | 3 ms
5,248 KB |
testcase_29 | AC | 3 ms
5,248 KB |
testcase_30 | AC | 3 ms
5,248 KB |
testcase_31 | AC | 2 ms
5,248 KB |
testcase_32 | AC | 2 ms
5,248 KB |
testcase_33 | AC | 2 ms
5,248 KB |
testcase_34 | AC | 2 ms
5,248 KB |
testcase_35 | AC | 2 ms
5,248 KB |
testcase_36 | AC | 2 ms
5,248 KB |
testcase_37 | AC | 2 ms
5,248 KB |
testcase_38 | AC | 2 ms
5,248 KB |
testcase_39 | AC | 2 ms
5,248 KB |
testcase_40 | AC | 2 ms
5,248 KB |
testcase_41 | AC | 2 ms
5,248 KB |
testcase_42 | AC | 2 ms
5,248 KB |
testcase_43 | AC | 2 ms
5,248 KB |
testcase_44 | AC | 2 ms
5,248 KB |
testcase_45 | AC | 2 ms
5,248 KB |
testcase_46 | AC | 3 ms
5,248 KB |
testcase_47 | AC | 2 ms
5,248 KB |
testcase_48 | AC | 2 ms
5,248 KB |
testcase_49 | AC | 2 ms
5,248 KB |
testcase_50 | AC | 2 ms
5,248 KB |
testcase_51 | AC | 2 ms
5,248 KB |
testcase_52 | AC | 2 ms
5,248 KB |
testcase_53 | AC | 2 ms
5,248 KB |
testcase_54 | AC | 2 ms
5,248 KB |
testcase_55 | AC | 2 ms
5,248 KB |
testcase_56 | AC | 2 ms
5,248 KB |
testcase_57 | AC | 2 ms
5,248 KB |
testcase_58 | AC | 2 ms
5,248 KB |
testcase_59 | AC | 2 ms
5,248 KB |
testcase_60 | AC | 2 ms
5,248 KB |
testcase_61 | AC | 2 ms
5,248 KB |
testcase_62 | AC | 2 ms
5,248 KB |
testcase_63 | AC | 2 ms
5,248 KB |
testcase_64 | AC | 2 ms
5,248 KB |
testcase_65 | AC | 2 ms
5,248 KB |
testcase_66 | AC | 2 ms
5,248 KB |
testcase_67 | AC | 2 ms
5,248 KB |
ソースコード
#include <cassert>#include <cstdio>#include <cinttypes>#include <unistd.h>#include <sys/stat.h>#include <sys/mman.h>class StrictInput{char *p;off_t cur = 0;off_t len = 0;public:explicit StrictInput(int fd = 0){struct stat st;fstat(fd, &st);p = (char *)mmap(NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);len = st.st_size;}char readChar(){assert(cur != len);return p[cur++];}void unreadChar(){assert(cur != 0);--cur;}bool isEof() { return cur == len; }void readEof() { assert(isEof()); }void readSpace() { assert(readChar() == ' '); }void readEoln() { assert(readChar() == '\n'); }// reads uint64_t in range [from, to]uint64_t readU64(uint64_t from = 0, uint64_t to = UINT64_MAX){uint64_t cur = 0;off_t read_cnt = 0;bool leading_zero = false;while (!isEof()){char p = readChar();if (!('0' <= p && p <= '9')){unreadChar();break;}uint64_t v = p - '0';assert(cur <= UINT64_MAX / 10);cur *= 10;assert(cur <= UINT64_MAX - v);cur += v;if (read_cnt == 0 && v == 0)leading_zero = true;++read_cnt;}if (cur == 0)assert(read_cnt == 1);elseassert(!leading_zero);assert(from <= cur && cur <= to);return cur;}// reads int64_t in range [from, to]int64_t readI64(int64_t from = INT64_MIN, int64_t to = INT64_MAX){uint64_t cur = 0;off_t read_cnt = 0;bool leading_zero = false;bool leading_minus = readChar() == '-';if (!leading_minus)unreadChar();while (!isEof()){char p = readChar();if (!('0' <= p && p <= '9')){unreadChar();break;}uint64_t v = p - '0';assert(cur <= UINT64_MAX / 10);cur *= 10;assert(cur <= UINT64_MAX - v);cur += v;if (read_cnt == 0 && v == 0)leading_zero = true;++read_cnt;}if (cur == 0)assert(read_cnt == 1 && !leading_minus);elseassert(!leading_zero);if (cur <= INT64_MAX){int64_t ret = cur;if (leading_minus)ret = -ret;assert(from <= ret && ret <= to);return ret;}else{assert(leading_minus && cur == uint64_t(INT64_MIN));assert(from == INT64_MIN);return INT64_MIN;}}};#include <algorithm>#include <vector>#include <atcoder/maxflow>using namespace std;int main(){StrictInput inf;int N, M, K, P;N = inf.readU64(1, 50);inf.readSpace();M = inf.readU64(1, 50);inf.readSpace();K = inf.readU64(1, 50);inf.readSpace();P = inf.readU64(0, N * M);inf.readEoln();vector<int> E(N);for (int i = 0; i < N; i++){E[i] = inf.readU64(1, 1'000'000'000);if (i == N - 1)inf.readEoln();elseinf.readSpace();}vector<int> F(M);for (int j = 0; j < M; j++){F[j] = inf.readU64(1, 1'000'000'000);if (j == M - 1)inf.readEoln();elseinf.readSpace();}vector<int> V(K);for (int k = 0; k < K; k++){V[k] = inf.readU64(1, 1'000'000'000);if (k == K - 1)inf.readEoln();elseinf.readSpace();}vector<vector<int>> A(N);for (int i = 0; i < N; i++){int L = inf.readU64(0, K);A[i].resize(L);int p = 0;for (int t = 0; t < L; t++){inf.readSpace();A[i][t] = inf.readU64(p + 1, K);p = A[i][t];A[i][t]--;}inf.readEoln();}vector<pair<int, int>> IJ(P);for (int t = 0; t < P; t++){IJ[t].first = inf.readU64(1, N);inf.readSpace();IJ[t].second = inf.readU64(1, M);inf.readEoln();IJ[t].first--;IJ[t].second--;}inf.readEof();sort(IJ.begin(), IJ.end());assert(unique(IJ.begin(), IJ.end()) == IJ.end());atcoder::mf_graph<long long> G(N + M + K + 2);int Goal = 0, Action = N, Preparation = N + M;int Source = N + M + K, Sink = N + M + K + 1;long long INF = 1e18;long long ans = 0;// Source~Goal: Goal i is achieved.for (int i = 0; i < N; i++){ans += E[i];G.add_edge(Source, Goal + i, E[i]);}// Action~Sink: Action i is achievedfor (int j = 0; j < M; j++){ans += F[j];G.add_edge(Action + j, Sink, F[j]);}// Source~Preparation: Preparation i is achievedfor (int k = 0; k < K; k++)G.add_edge(Preparation + k, Sink, V[k]);// If Source->Goal exists, Source->Preparation should also existfor (int i = 0; i < N; i++)for (int k : A[i])G.add_edge(Goal + i, Preparation + k, INF);// If Source->Goal exists, Source->Action should also existfor (auto [I, J] : IJ)G.add_edge(Goal + I, Action + J, INF);// Min cut should be deducted from maxflowans -= G.flow(Source, Sink);int cnt = 0;vector<bool> cut = G.min_cut(Source);vector<bool> goal(N), action(M), preparation(K);for (int i = 0; i < N; i++)cnt += (goal[i] = cut[Goal + i]);for (int j = 0; j < M; j++)cnt += (action[j] = !cut[Action + j]);for (int k = 0; k < K; k++)cnt += (preparation[k] = cut[Preparation + k]);printf("%lld\n", ans);printf("%d\n", cnt);// Do all preparations firstfor (int i = 0; i < K; i++)if (preparation[i])printf("Preparation %d\n", 1 + i);// Others can be done arbitarilyfor (int j = 0; j < N; j++)if (goal[j])printf("Goal %d\n", 1 + j);for (int k = 0; k < M; k++)if (action[k])printf("Action %d\n", 1 + k);return 0;}