結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー tubo28
提出日時 2016-12-20 02:14:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,631 bytes
コンパイル時間 3,198 ms
コンパイル使用メモリ 200,256 KB
実行使用メモリ 546,964 KB
最終ジャッジ日時 2024-12-22 13:23:52
合計ジャッジ時間 19,142 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 4
other MLE * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(c) begin(c), end(c)
#define dump(x) cerr << __LINE__ << ":\t" #x " = " << (x) << endl

using Weight = int;
using Cap = int;
struct Edge {
    int src, dst;
    Cap cap;
    Edge(int s, int d, Cap c) : src(s), dst(d), cap(c) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

struct dinic {
    int n, s, t;
    vector<int> level, prog, que;
    vector<vector<Cap>> cap, flow;
    vector<vector<int>> g;
    Cap inf;
    dinic(const Graph &graph)
        : n(graph.size()),
        cap(n, vector<Cap>(n)),
        flow(n, vector<Cap>(n)),
        g(n, vector<int>()),
        inf(numeric_limits<Cap>::max() / 8) {
        for (int i = 0; i < n; i++) {
            for (auto &e : graph[i]) {
                int u = e.src, v = e.dst;
                Cap c = e.cap;
                cap[u][v] += c;
                cap[v][u] += c;
                flow[v][u] += c;
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
    }
    inline Cap residue(int u, int v) { return cap[u][v] - flow[u][v]; }
    Cap solve(int s_, int t_) {
        this->t = t_, this->s = s_;
        que.resize(n + 1);
        Cap res = 0;
        while (levelize()) {
            prog.assign(n, 0);
            res += augment(s, inf);
        }
        return res;
    }
    bool levelize() {
        int l = 0, r = 0;
        level.assign(n, -1);
        level[s] = 0;
        que[r++] = s;
        while (l != r) {
            int v = que[l++];
            if (v == t) break;
            for (const int &d : g[v])
                if (level[d] == -1 && residue(v, d) != 0) {
                    level[d] = level[v] + 1;
                    que[r++] = d;
                }
        }
        return level[t] != -1;
    }
    Cap augment(int v, Cap lim) {
        Cap res = 0;
        if (v == t) return lim;
        for (int &i = prog[v]; i < (int)g[v].size(); i++) {
            const int &d = g[v][i];
            if (residue(v, d) == 0 || level[v] >= level[d]) continue;
            const Cap aug = augment(d, min(lim, residue(v, d)));
            flow[v][d] += aug;
            flow[d][v] -= aug;
            res += aug;
            lim -= aug;
            if (lim == 0) break;
        }
        return res;
    }
};

int main() {
    vector<char> alpha;
    for (char c = 'A'; c <= 'Z'; ++c) {
        alpha.push_back(c);
    }
    for (char c = 'a'; c <= 'z'; ++c) {
        alpha.push_back(c);
    }

    vector<string> vs;
    for (char c : alpha) {
        string s = { c };
        vs.push_back(s);
        for (char d : alpha) {
            string t = { c, d };
            vs.push_back(t);
        }
    }

    sort(vs.begin(), vs.end());
    auto id = [&](const string &s) {
        return lower_bound(all(vs), s) - vs.begin();
    };

    int n;
    while (cin >> n) {
        int N = vs.size() * 2 + vs.size() + 2;
        int S = N - 2;
        int T = N - 1;
        Graph g(N); // S->(1->2)*->T
        for (auto &v : vs) {
            if (v.size() == 1) {
                int i = id(v);
                g[S].emplace_back(S, i, 1);
            } else {
                int i = id(v);
                g[i].emplace_back(i, T, 1);
            }
        }

        vector<string> ss(n);
        for (int i = 0; i < n; i++) {
            string &s = ss[i];
            cin >> s;
            string a = s.substr(0, 1);
            string ab = s.substr(0, 2);
            string bc = s.substr(1, 2);
            string c = s.substr(2, 1);
            g[id(a)].emplace_back(id(a), id(bc), 1);
            g[id(c)].emplace_back(id(c), id(ab), 1);
        }

        dinic dn(g);
        int f = dn.solve(S, T);
        if (f >= n) {
            // cout << "possible" << endl;
            for (auto &s : ss) {
                string a = s.substr(0, 1);
                string bc = s.substr(1);
                int ia = id(a);
                int ibc = id(bc);
                
                string ab = s.substr(0, 2);
                string c = s.substr(2);
                int iab = id(ab);
                int ic = id(c);

                if (dn.flow[ia][ibc]) {
                    cout << a << ' ' << bc << '\n';
                    dn.flow[ia][ibc] = 0;
                } else if(dn.flow[ibc][ia]){
                    cout << ab << ' ' << c << '\n';
                    dn.flow[iab][ic] = 0;
                }
            }
        } else {
            cout << "Impossible" << '\n';
        }
    }
}
0