Codeforces 554 DIV2 E. Neko and Flashback (R2500)

面白かった

問題へのリンク

問題概要 (やや意訳)

長さ の数列 を復元したい。この数列に対し、ある並び替え順列 があって

• 隣り合う 2 要素の min をとってできる長さ の数列を で並び替えると となり
• 隣り合う 2 要素の max をとってできる長さ の数列を で並び替えると となっていた

ということのみがわかっている。並び替え方もわからない。元の数列として考えられるものを 1 つ求めよ。存在しえない場合は -1 を出力せよ。

制約

• 

考えたこと

順列系！面白そう！！
とりあえず

• min = p
• max = q

となっていたら、並び替えるまえの数列は と を含むことはわかる。仮に だったとしても を 2 個含むことがわかる。

ということを考えていくと、

• と を辺で結ぶ

ということを各 に対して行ってできるグラフにおいて一本のパスがとれるかどうかを考える問題となりそうなことがわかる。

より具体的には、Euler 路を求める問題になる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


// edge class (for network-flow)
template<class FLOWTYPE> struct Edge {
    int rev, from, to;
    FLOWTYPE cap, icap;
    Edge(int r, int f, int t, FLOWTYPE c) : rev(r), from(f), to(t), cap(c), icap(c) {}
    friend ostream& operator << (ostream& s, const Edge& E) {
        if (E.cap > 0) return s << E.from << "->" << E.to << '(' << E.cap << ')';
        else return s;
    }
};

// graph class (for network-flow)
template<class FLOWTYPE> struct Graph {
    vector<vector<Edge<FLOWTYPE> > > list;
    
    Graph(int n = 0) : list(n) { }
    void init(int n = 0) { list.clear(); list.resize(n); }
    void reset() { for (int i = 0; i < (int)list.size(); ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; }
    inline vector<Edge<FLOWTYPE> >& operator [] (int i) { return list[i]; }
    inline const size_t size() const { return list.size(); }
    
    inline Edge<FLOWTYPE> &redge(Edge<FLOWTYPE> e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    
    void addedge(int from, int to, FLOWTYPE cap) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0));
    }
    
    void add_undirected_edge(int from, int to, FLOWTYPE cap) {
        list[from].push_back(Edge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(Edge<FLOWTYPE>((int)list[from].size() - 1, to, from, cap));
    }

    /*
    // debug
    friend ostream& operator << (ostream& s, const Graph& G) {
        s << endl; for (int i = 0; i < G.size(); ++i) { s << i << " : " << G.list[i] << endl; }return s;
    }
    */
};

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

struct Euler {
    vector<int> nextv, walk;
    Euler() {}
    void dfs(Graph<int> &G, int v) {
        for (int &i = nextv[v]; i < (int)G[v].size(); ++i) {
            auto &e = G[v][i];
            if (e.cap == 0) continue;
            --e.cap;
            --G.redge(e).cap;
            dfs(G, e.to);
        }
        walk.push_back(v);
    }
    vector<vector<int> > solve(Graph<int> &G) {
        vector<vector<int> > res;
        int V = (int)G.size();
        UnionFind uf(V);
        for (int v = 0; v < V; ++v) for (auto e : G[v]) uf.merge(e.from, e.to);
        vector<vector<int> > comps(V);
        for (int v = 0; v < V; ++v) {
            int r = uf.root(v);
            comps[r].push_back(v);
        }
        nextv.assign(V, 0);
        for (int v = 0; v < V; ++v) {
            if (comps[v].empty()) continue;
            vector<int> odds;
            for (auto v2 : comps[v]) if (G[v2].size() & 1) odds.push_back(v2);
            if (odds.size() > 2) return vector<vector<int> >();
            walk.clear();
            int start = (!odds.empty() ? odds[0] : v);
            dfs(G, start);
            reverse(walk.begin(), walk.end());
            res.push_back(walk);
        }
        return res;
    }
};


void solve(const vector<int> &a, const vector<int> &b) {
    vector<int> vals;
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] > b[i]) {
            cout << -1 << endl;
            return;
        }
        vals.push_back(a[i]);
        vals.push_back(b[i]);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    Graph<int> G((int)vals.size());
    for (int i = 0; i < (int)a.size(); ++i) {
        int ai = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
        int bi = lower_bound(vals.begin(), vals.end(), b[i]) - vals.begin();
        G.add_undirected_edge(ai, bi, 1);
    }
    Euler el;
    auto res = el.solve(G);
    if (res.empty() || res.size() > 1) {
        cout << -1 << endl;
        return;
    }
    for (int i = 0; i < (int)res[0].size(); ++i) {
        if (i) cout << " ";
        cout << vals[res[0][i]];
    }
    cout << endl;
}

int main() {
    int N;
    while (cin >> N) {
        vector<int> a(N-1), b(N-1);
        for (int i = 0; i < N-1; ++i) cin >> a[i];
        for (int i = 0; i < N-1; ++i) cin >> b[i];
        solve(a, b);
    }
}