結果

問題 No.1984 [Cherry 4th Tune *] Dilemma
ユーザー colognecologne
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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);
else
assert(!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);
else
assert(!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();
else
inf.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();
else
inf.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();
else
inf.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 achieved
for (int j = 0; j < M; j++)
{
ans += F[j];
G.add_edge(Action + j, Sink, F[j]);
}
// Source~Preparation: Preparation i is achieved
for (int k = 0; k < K; k++)
G.add_edge(Preparation + k, Sink, V[k]);
// If Source->Goal exists, Source->Preparation should also exist
for (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 exist
for (auto [I, J] : IJ)
G.add_edge(Goal + I, Action + J, INF);
// Min cut should be deducted from maxflow
ans -= 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 first
for (int i = 0; i < K; i++)
if (preparation[i])
printf("Preparation %d\n", 1 + i);
// Others can be done arbitarily
for (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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0