結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 68
権限があれば一括ダウンロードができます

ソースコード

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;
}
0