結果

問題 No.459 C-VS for yukicoder
ユーザー mai(舞葉)
提出日時 2017-05-07 00:20:25
言語 C++17(1z)
(gcc 7.2.0)
結果
AC  
実行時間 93 ms
コード長 14,377 Byte
コンパイル時間 1,790 ms
使用メモリ 1,676 KB
最終ジャッジ日時 2017-05-07 00:20:34

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0sample1.txt AC 4 ms
1,536 KB
0sample2.txt AC 3 ms
1,532 KB
0sample3.txt AC 3 ms
1,532 KB
1simple0.txt AC 2 ms
1,520 KB
1simple1.txt AC 3 ms
1,516 KB
1simple2.txt AC 3 ms
1,516 KB
1simple3.txt AC 2 ms
1,532 KB
1simple4.txt AC 4 ms
1,532 KB
1simple5.txt AC 4 ms
1,528 KB
1simple6.txt AC 2 ms
1,532 KB
1simple7.txt AC 3 ms
1,532 KB
1simple8.txt AC 3 ms
1,528 KB
1simple9.txt AC 3 ms
1,528 KB
1simple10.txt AC 3 ms
1,532 KB
1simple11.txt AC 2 ms
1,532 KB
2random1.txt AC 4 ms
1,560 KB
2random2.txt AC 3 ms
1,552 KB
2random3.txt AC 4 ms
1,548 KB
2random4.txt AC 3 ms
1,552 KB
2random5.txt AC 2 ms
1,548 KB
2random6.txt AC 4 ms
1,548 KB
5extreme0.txt AC 75 ms
1,676 KB
5extreme1.txt AC 48 ms
1,672 KB
5extreme2.txt AC 93 ms
1,664 KB
5extreme3.txt AC 25 ms
1,660 KB
5extreme4.txt AC 13 ms
1,612 KB
5extreme5.txt AC 10 ms
1,568 KB
5extreme6.txt AC 9 ms
1,580 KB
5extreme7.txt AC 13 ms
1,616 KB
5extreme8.txt AC 20 ms
1,652 KB
5extreme9.txt AC 10 ms
1,568 KB
6random1.txt AC 16 ms
1,616 KB
6random2.txt AC 4 ms
1,576 KB
6random3.txt AC 20 ms
1,640 KB
6random4.txt AC 20 ms
1,636 KB
6random5.txt AC 6 ms
1,580 KB
6random6.txt AC 17 ms
1,612 KB
6random7.txt AC 6 ms
1,572 KB
6random8.txt AC 19 ms
1,632 KB
6random9.txt AC 5 ms
1,560 KB
6random10.txt AC 14 ms
1,608 KB
6random11.txt AC 4 ms
1,580 KB
6random12.txt AC 12 ms
1,608 KB
6random13.txt AC 18 ms
1,624 KB
6random14.txt AC 8 ms
1,568 KB
6random15.txt AC 5 ms
1,568 KB
6random16.txt AC 7 ms
1,560 KB
6random17.txt AC 4 ms
1,560 KB
6random18.txt AC 18 ms
1,624 KB
6random19.txt AC 5 ms
1,584 KB
6random20.txt AC 17 ms
1,628 KB
gen_case1.txt AC 6 ms
1,576 KB
gen_case2.txt AC 11 ms
1,584 KB
gen_case3.txt AC 6 ms
1,564 KB
gen_case4.txt AC 19 ms
1,636 KB
gen_case5.txt AC 7 ms
1,560 KB
gen_case6.txt AC 13 ms
1,604 KB
gen_case7.txt AC 5 ms
1,584 KB
gen_case8.txt AC 20 ms
1,628 KB
gen_case9.txt AC 7 ms
1,572 KB
gen_case10.txt AC 9 ms
1,584 KB
テストケース一括ダウンロード

ソースコード

diff #
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include "bits/stdc++.h" // define macro "/D__MAI"

using namespace std;
typedef unsigned int uint;
typedef long long int ll;
typedef unsigned long long int ull;

#define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;
#define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;}
#define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;
#define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;}
#define debugaar(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}
#define ALL(v) (v).begin(),(v).end()
#define repeat(l) for(auto cnt=0;cnt<(l);++cnt)
#define upto(l,r) for(auto cnt=l;cnt<=r;++cnt)
#define downto(r,l) for(auti cnt=r;cnt>=l;--cnt)
#define BIGINT 0x7FFFFFFF
#define MD 1000000007ll
#define PI 3.1415926535897932384626433832795
template <typename T1, typename T2>
ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o; }
#define TIME chrono::system_clock::now()
#define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count())
namespace {
    std::chrono::system_clock::time_point ttt;
    void tic() { ttt = TIME; }
    void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - ttt)); }
    std::chrono::system_clock::time_point tle = TIME;
#ifdef __MAI
    void safe_tle(int msec) { assert(MILLISEC(TIME - tle) < msec); }
#else
#define safe_tle(k) ;
#endif
}

#ifdef __MAI //_getchar_nolock
#define getchar_unlocked getchar
#endif
namespace {
    class MaiScanner {
    public:
        template<typename T>
        void input_integer(T& var) {
            var = 0;
            T sign = 1;
            int cc = getchar_unlocked();
            for (; cc<'0' || '9'<cc; cc = getchar_unlocked())
                if (cc == '-') sign = -1;
            for (; '0' <= cc&&cc <= '9'; cc = getchar_unlocked())
                var = (var << 3) + (var << 1) + cc - '0';
            var = var*sign;
        }
        inline int c() { return getchar_unlocked(); }
        inline MaiScanner& operator>>(int& var) {
            input_integer<int>(var);
            return *this;
        }
        inline MaiScanner& operator>>(long long& var) {
            input_integer<long long>(var);
            return *this;
        }
    };
}
MaiScanner scanner;

namespace std {
    template<typename T1, typename T2>
    class hash<pair<T1, T2>> {
    public:
        size_t operator()(const pair<T1, T2>& x) const {
            return hash<T1>()(x.first) ^ hash<T2>()(x.second);
        }
    };
}
// todo : typedef int_c int // capacity

// TODO:マーカーの実装?
class Flow {
public:
    size_t n;
    struct Arrow {
        int from, to;
        int w_max; // TODO: leftに改名
        int cap;

        Arrow(int from = 0, int to = 0, int w = 1) :from(from), to(to), w_max(w), cap(w) {}
    };
    vector<vector<int>> vertex_to;
    vector<vector<int>> vertex_from;
    vector<Arrow> arrow;

    Flow(int n, int m = 5010) :n(n), vertex_to(n), vertex_from(n) { arrow.reserve(m); }

    void connect(int from, int to, int w_max) {
        vertex_to[from].push_back(arrow.size()); // toto
        vertex_from[to].push_back(arrow.size()); // fromfrom
        arrow.emplace_back(from, to, w_max);
    }
    size_t degree(int v) {
        return vertex_to[v].size() + vertex_from[v].size();
    }
    size_t degree_in(int v) {
        return vertex_from[v].size();
    }
    size_t degree_out(int v) {
        return vertex_to[v].size();
    }
};

int statics_a;
int statics_b;
int statics_c;
// DAG
int _dinic_path_dfs(Flow& flow, vector<int>& result, vector<int>& flag, const vector<int>& dist, int u, int i_sink, int mini) {
    // TODO: 経路再利用
    if (i_sink == u) return mini;
    if (flag[u]) return -1;
    flag[u] = true;

    ++statics_a;

    int sumw = 0;
    bool term = true;
    for (int e : flow.vertex_to[u]) {
        Flow::Arrow& a = flow.arrow[e];
        if (a.w_max > 0 && dist[u]>dist[a.to]) {
            int w;
            if (mini < 0)
                w = a.w_max;
            else
                w = min(a.w_max, mini);

            w = _dinic_path_dfs(flow, result, flag, dist, a.to, i_sink, w);
            if (w == -1) continue;
            a.w_max -= w;
            result[a.to] += w;

            //printf("%d->%d (%d) : w=%d mini=%d \n",a.from,a.to,a.w_max+w,w,mini);

            sumw += w;
            mini -= w;
            term = false;
            flag[u] = false;

            ++statics_b;
            statics_c+=w==0; // !!!!(゚д゚)!!!!
            if (mini == 0) break; // !!!!(゚д゚)!!!!
        }
    }
    if (mini == 0) return term ? -1 : sumw; // !!!!(゚д゚)!!!!
    for (int e : flow.vertex_from[u]) {
        Flow::Arrow& a = flow.arrow[e];
        if (a.cap>a.w_max && dist[u]>dist[a.from]) {
            int w;
            if (mini < 0)
                w = a.cap - a.w_max;
            else
                w = min(a.cap - a.w_max, mini);

            w = _dinic_path_dfs(flow, result, flag, dist, a.from, i_sink, w);
            if (w == -1) continue;
            a.w_max += w;
            result[a.to] -= w;

            //printf("%d<-%d (%d) : w=%d mini=%d \n",a.from,a.to,a.w_max-w,w,mini);

            sumw += w;
            mini -= w;
            term = false;
            flag[u] = false;
            if (mini == 0) break; // !!!!(゚д゚)!!!!

        }
    }
    return term ? -1 : sumw;
}

// flowは書き換えられる.
void dinic(Flow &flow, vector<int>& result, int i_source, int i_sink) {
    assert(i_source != i_sink);

    result.resize(flow.n);

    int distbegin = 0;
    vector<int> dist(flow.n);
    queue<int> q;
    vector<int> flag(flow.n);
    tic();
    for (int distbegin = 0; ; distbegin += flow.n) {

        q.emplace(i_sink); // bfsはsinkからsourceへの距離を計算.
        dist[i_sink] = distbegin + 1;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int ie : flow.vertex_from[v]) {
                const Flow::Arrow& e = flow.arrow[ie];
                if (0<e.w_max && dist[e.from] <= distbegin) {
                    dist[e.from] = dist[v] + 1;
                    q.emplace(e.from);
                }
            }
            for (int ie : flow.vertex_to[v]) {
                const Flow::Arrow& e = flow.arrow[ie];
                if (e.w_max<e.cap && dist[e.to] <= distbegin) {
                    dist[e.to] = dist[v] + 1;
                    q.emplace(e.to);
                }
            }
        }
        cerr << distbegin << endl;
        toc();
        //debugv(dist);
        fill(ALL(flag), false);

        if (dist[i_source] <= distbegin) {
            break;
        }
        else {
            result[i_source] += _dinic_path_dfs(flow, result, flag, dist, i_source, i_sink, -1);
        }
        fprintf(stderr, "statics %d %d %d\n", statics_a, statics_b, statics_c);
        toc();
    }

}

// 最大最小流量制限付き
class FlowMinMax {
public:
    Flow flow;
    int ss; // vertex of new source

    FlowMinMax(int n, int m) :flow(n + 2, m), ss(n) {}
    FlowMinMax(int n) :flow(n + 2), ss(n) {}

    void connect(int from, int to, int w_min, int w_max) {
        // assert(w_min < w_max);
        /*
        flow.connect(from, ss+1, w_min);
        flow.connect(from, to  , w_max-w_min);
        flow.connect(ss  , to  , w_min);
        return;
        */

        if (w_max == w_min) {
            flow.connect(ss, to, w_min);
            flow.connect(from, ss + 1, w_min);
        }
        else if (w_min == 0) {
            flow.connect(from, to, w_max - w_min);
        }
        else {
            flow.connect(from, ss + 1, w_min);
            flow.connect(from, to, w_max - w_min);
            flow.connect(ss, to, w_min);
        }
    }
private:
    template<typename MAP_PI> // map<pair<int,int>,int> or unordered_map
    bool _solve_dinic_edge(MAP_PI& result_edge, int i_source, int i_sink) {

        vector<int> resflow(flow.n, 0);

        dinic(flow, resflow, ss, ss + 1);
        dinic(flow, resflow, ss, i_sink);
        dinic(flow, resflow, i_source, ss + 1);
        dinic(flow, resflow, i_source, i_sink);

        for (int e : flow.vertex_from[ss + 1]) {
            const Flow::Arrow& a = flow.arrow[e];
            //printf("%d->%d (%d)\n",a.from,a.to,a.w_max);cout.flush();
            if (0 < a.w_max) return false;
        }
        int floow;
        for (int u = 0; u<flow.n - 2; u++) {
            for (int ea : flow.vertex_to[u]) { // TODO:無駄っぽい(2回参照)
                const Flow::Arrow& a = flow.arrow[ea]; // u -> v
                if (a.to >= flow.n - 2) {
                    if (0 < a.w_max) return false;
                    continue;
                }

                const Flow::Arrow& c = flow.arrow[ea + 1]; // S -> v
                if (a.to != c.to) {
                    floow = a.cap - a.w_max;
                }
                else {
                    if (0 < c.w_max) return false;
                    floow = c.cap + a.cap - c.w_max - a.w_max;
                }
                if (0 < floow)
                    result_edge[make_pair(u, a.to)] += floow;
            }
        }
        return true;
    }
    // connect操作を行うので,2回以上呼び出すのは禁止
    // sumflow = sink,flowの流量が既知
    template<typename MAP_PI>
    bool _solve_dinic_edge_known(MAP_PI& result_edge, int i_source, int i_sink, int sumflow) {
        vector<int> resflow(flow.n, 0);

        flow.connect(ss, i_source, sumflow);
        flow.connect(i_sink, ss + 1, sumflow);

        dinic(flow, resflow, ss, ss + 1);


        for (int e : flow.vertex_from[ss + 1]) {
            const Flow::Arrow& a = flow.arrow[e];
            //printf("%d->%d (%d)\n",a.from,a.to,a.w_max);cout.flush();
            if (0 < a.w_max) return false;
        }
        int floow;
        for (int u = 0; u<flow.n - 2; u++) {
            for (int ea : flow.vertex_to[u]) { // TODO:無駄っぽい(2回参照)
                const Flow::Arrow& a = flow.arrow[ea]; // u -> v
                if (a.to >= flow.n - 2) {
                    if (0 < a.w_max) return false;
                    continue;
                }

                const Flow::Arrow& c = flow.arrow[ea + 1]; // S -> v
                if (a.to != c.to) {
                    floow = a.cap - a.w_max;
                }
                else {
                    if (0 < c.w_max) return false;
                    floow = c.cap + a.cap - c.w_max - a.w_max;
                }
                if (0 < floow)
                    result_edge[make_pair(u, a.to)] += floow;
            }
        }
        return true;
    }

public:
    bool solve_dinic_edge(map<pair<int, int>, int>& result_edge, int i_source, int i_sink, int sumflow = -1) {
        return sumflow<0 ? _solve_dinic_edge(result_edge, i_source, i_sink)
            : _solve_dinic_edge_known(result_edge, i_source, i_sink, sumflow);
    }
    bool solve_dinic_edge(unordered_map<pair<int, int>, int>& result_edge, int i_source, int i_sink, int sumflow = -1) {
        return sumflow<0 ? _solve_dinic_edge(result_edge, i_source, i_sink)
            : _solve_dinic_edge_known(result_edge, i_source, i_sink, sumflow);
    }

};

/**
// dinic sample
int main(){
int i,j,k;
int x,y,a,b;

Flow graph(6);

graph.connect(0,1,1);
graph.connect(1,4,1);
graph.connect(4,5,1);
graph.connect(0,3,1);
graph.connect(3,4,1);
graph.connect(1,2,1);
graph.connect(2,5,1);

vector<int> result(6,0);
dinic(graph,result,0,5);

debugv(result);

// FlowMinMax graph2(3);
//
// graph2.connect(0,1,1,2);
// graph2.connect(1,2,3,4);
//
// vector<int> result2(3,0);
// cout << (graph2.solve_dinic(result2,0,2) ? "true" : "false") << endl;
//
// debugv(result2);

return 0;
}
/**/
/**/

int width, height;
int m, n;

int field[10010];
int commands[30010];

int main() {
    int i, j, k;
    int x, y, a, b;

    cin >> height >> width >> n;
    cin.ignore();

    int nblocks = 0;
    // X座標にブロックがいくつ積まれているか、を記録する。
    // stringを保持する必要はない。
    for (y = 0; y < height; y++) {
        string s;
        cin >> s;
        for (x = 0; x < width; x++) {
            field[x] += s[x] == '#';
        }
    }
    for (x = 0; x < width; x++) { nblocks += field[x]; }

    for (i = 0; i < n; i++) {
        scanf("%d", commands + i);
    }

    //          A   _    B    _   C
    //             | | ----> | | ----> [sink]
    // [source] -> | |       | |
    //             | |       | |
    //             |_pack    |_field
    // 
    // A : [1,9] (packは[1,9]個のブロックを持つ)
    // B : [0,3] (packは3x3の容量を持つ)
    // C : [#,#] (x列には#個のブロックが積み上がっている)

    FlowMinMax flow(1 + n + width + 1);

    const int i_source = 0;
    const int i_sink = 1;

    for (i = 0; i < n; i++) {
        // A edge
        flow.connect(i_source, 2 + i, 1, 9);
        int left = commands[i];
        for (j = 0; j < 3; j++) {
            // B edge
            flow.connect(2 + i, 2 + n + left + j, 0, 3);
        }
    }
    for (x = 0; x < width; x++) {
        // C edge
        flow.connect(2 + n + x, i_sink, field[x], field[x]);
    }

    //for (Flow::Arrow& ar : flow.flow.arrow){
    //    if (ar.w_max == 0) continue;
    //    printf("%d -> %d\n",ar.from,ar.to);
    //}

    unordered_map<pair<int, int>, int> nagare;
    if (!flow.solve_dinic_edge(nagare, i_source, i_sink, nblocks)) {
        abort();
        cout << "warn" << endl;
    }

    //debugv(nagare);

    int hako[3];
    for (i = 0; i < n; i++) {
        for (j = 0; j < 3; j++) {
            hako[j] = nagare[make_pair(2 + i, 2 + n + commands[i] + j)];
        }
        for (y = 3; 0 < y; y--) {
            for (x = 0; x < 3; x++) {
                if (y <= hako[x]) {
                    putchar('#');
                }
                else {
                    putchar('.');
                }
            }
            putchar('\n');
        }
    }


    return 0;
}

/*
2 4 3
..#.
..##
0
1
0
*/
0