結果

問題 No.459 C-VS for yukicoder
ユーザー 舞葉
提出日時 2017-05-07 00:20:25
言語 C++17(1z)
(gcc 6.3.0)
結果
AC  
実行時間 93 ms
コード長 14377 Byte
コンパイル時間 1790 ms
使用メモリ 1676 KB

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0sample1.txt AC 4 ms
1536 KB
0sample2.txt AC 3 ms
1532 KB
0sample3.txt AC 3 ms
1532 KB
1simple0.txt AC 2 ms
1520 KB
1simple1.txt AC 3 ms
1516 KB
1simple2.txt AC 3 ms
1516 KB
1simple3.txt AC 2 ms
1532 KB
1simple4.txt AC 4 ms
1532 KB
1simple5.txt AC 4 ms
1528 KB
1simple6.txt AC 2 ms
1532 KB
1simple7.txt AC 3 ms
1532 KB
1simple8.txt AC 3 ms
1528 KB
1simple9.txt AC 3 ms
1528 KB
1simple10.txt AC 3 ms
1532 KB
1simple11.txt AC 2 ms
1532 KB
2random1.txt AC 4 ms
1560 KB
2random2.txt AC 3 ms
1552 KB
2random3.txt AC 4 ms
1548 KB
2random4.txt AC 3 ms
1552 KB
2random5.txt AC 2 ms
1548 KB
2random6.txt AC 4 ms
1548 KB
5extreme0.txt AC 75 ms
1676 KB
5extreme1.txt AC 48 ms
1672 KB
5extreme2.txt AC 93 ms
1664 KB
5extreme3.txt AC 25 ms
1660 KB
5extreme4.txt AC 13 ms
1612 KB
5extreme5.txt AC 10 ms
1568 KB
5extreme6.txt AC 9 ms
1580 KB
5extreme7.txt AC 13 ms
1616 KB
5extreme8.txt AC 20 ms
1652 KB
5extreme9.txt AC 10 ms
1568 KB
6random1.txt AC 16 ms
1616 KB
6random2.txt AC 4 ms
1576 KB
6random3.txt AC 20 ms
1640 KB
6random4.txt AC 20 ms
1636 KB
6random5.txt AC 6 ms
1580 KB
6random6.txt AC 17 ms
1612 KB
6random7.txt AC 6 ms
1572 KB
6random8.txt AC 19 ms
1632 KB
6random9.txt AC 5 ms
1560 KB
6random10.txt AC 14 ms
1608 KB
6random11.txt AC 4 ms
1580 KB
6random12.txt AC 12 ms
1608 KB
6random13.txt AC 18 ms
1624 KB
6random14.txt AC 8 ms
1568 KB
6random15.txt AC 5 ms
1568 KB
6random16.txt AC 7 ms
1560 KB
6random17.txt AC 4 ms
1560 KB
6random18.txt AC 18 ms
1624 KB
6random19.txt AC 5 ms
1584 KB
6random20.txt AC 17 ms
1628 KB
gen_case1.txt AC 6 ms
1576 KB
gen_case2.txt AC 11 ms
1584 KB
gen_case3.txt AC 6 ms
1564 KB
gen_case4.txt AC 19 ms
1636 KB
gen_case5.txt AC 7 ms
1560 KB
gen_case6.txt AC 13 ms
1604 KB
gen_case7.txt AC 5 ms
1584 KB
gen_case8.txt AC 20 ms
1628 KB
gen_case9.txt AC 7 ms
1572 KB
gen_case10.txt AC 9 ms
1584 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