← Real problems

egoi23p7

unratedStatement on DMOJ

CP Lang

50 lines0.3 spec
use std.graph.complement
// egoi23p7 Find the Tree: a spanning arborescence that uses every required arc and no
// forbidden one. Required arcs must already form a forest; each of its trees is one block that
// must hang from some other block. Block c can hang under block k unless every vertex of k is
// forbidden as the parent of c's root, so the blocks need a spanning arborescence of the
// complement of those "fully blocked" arcs: the root of the last tree a DFS of it starts
// reaches everything if anything does.
let (n, m1, m2) = read<(1..=300_000, 0..=300_000, 0..=300_000)>()
domain V = [n]
let must = read<[m1](child: V, parent: V)>()
let banned = read<[m2](child: V, parent: V)>()

fn solve() -> ?List<(child: V, parent: V)>:
    var up: [V]?V = None
    for e in must:
        if up[e.child] != None:
            return None
        up[e.child] = Some(e.parent)
    let forest = Rooted.try_from_parents(up) else: return None
    let (domain B, top) = compress(forest.roots)
    let block = [V] v => top.at(forest.root_of(v))!
    let members = block.buckets()
    var forbidden: [V]HashSet<V> = HashSet()
    for e in banned:
        forbidden[e.child].add(e.parent)
    var blocked: [B]List<B> = []
    for c in B:
        for (k, hits) in forbidden[top.get(c)].tally(by: v => block[v]).items:
            if hits == members[k].len:
                blocked[k].push(c)
    let hang = complement(blocked)
    // The last vertex a DFS finishes is the only block that can reach all the others.
    var root = B.first!
    for step in dfs(hang, from: B) if step is Exit(b, _):
        root = b
    let tree = bfs(hang, from: [root])
    if B.any(b => not tree.reached(b)):
        return None
    var out = List(must)
    for b in B if b != root:
        let k = tree.back[b]!.from
        let c = top.get(b)
        out.push((child: c, parent: members[k].find(x => x not in forbidden[c])!))
    out

if let arcs = solve():
    for a in arcs:
        print(a.child, a.parent)
else:
    print("NO")

Accepted C++

233 lines · 13.48 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

struct Solver {
    int n;
    vector<char> vis, has_par;
    set<int> to_vis;
    vector<pair<int, int>> dfs_tree;
    vector<vector<int>> graph;

    Solver(int n, const vector<pair<int, int>>& edges)
        : n(n), vis(n), has_par(n), graph(n) {
        for (auto& [u, v] : edges) {
            graph[u].push_back(v);
        }
        for (int i = 0; i < n; i++) {
            to_vis.insert(i);
        }
        for (int i = 0; i < n; i++) {
            if (to_vis.count(i)) {
                to_vis.erase(i);
                dfs(i, -1);
                to_vis.insert(i);
            }
        }
    }

    void dfs(int u, int p) {
        assert(!has_par[u]);
        if (p != -1) {
            has_par[u] = true;
            dfs_tree.emplace_back(p, u);
        }
        if (vis[u]) {
            return;
        }
        vis[u] = true;

        set<int> can_vis, cant_vis;
        swap(can_vis, to_vis);
        for (auto& v : graph[u]) {
            auto it = can_vis.find(v);
            if (it == can_vis.end()) {
                continue;
            }
            cant_vis.insert(v);
            can_vis.erase(it);
        }
        swap(cant_vis, to_vis);

        for (auto& v : can_vis) {
            dfs(v, u);
        }
    }
};

struct Checker {
    int n;
    vector<char> vis;
    vector<vector<int>> graph;

    Checker(const vector<pair<int, int>>& edges) : n(sz(edges) + 1),  vis(n), graph(n) {
        int ideg[n] {};
        for (auto& [u, v] : edges) {
            graph[u].push_back(v);
            ideg[v]++;
        }

        int zdeg = 0;
        for (int i = 0; i < n; i++) {
            zdeg += !ideg[i];
            if (!ideg[i]) {
                dfs(i);
            }
        }
        assert(zdeg == 1);

        assert(vis == vector<char>(n, true));
    }

    void dfs(int u) {
        assert(!vis[u]);
        vis[u] = true;
        for (auto& v : graph[u]) {
            dfs(v);
        }
    }
};

constexpr int maxn = 3e5 + 5;

bool has_cyc, vis[maxn];
vector<int> ord, graph[maxn];

void dfs(int u) {
    if (vis[u]) {
        has_cyc = true;
        return;
    }
    vis[u] = true;
    for (auto& v : graph[u]) {
        dfs(v);
    }
    ord.push_back(u);
}

void solve() {
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    vector<pair<int, int>> edges1(m1), edges2(m2);
    for (auto& [u, v] : edges1) {
        cin >> u >> v;
        swap(u, v);
    }
    for (auto& [u, v] : edges2) {
        cin >> u >> v;
        swap(u, v);
    }

    int ideg[n] {};
    for (auto& [u, v] : edges1) {
        graph[u].push_back(v);
        ideg[v]++;
    }

    int comp_id = 0, comp[n], rep[n];
    vector<int> comps[n];
    for (int i = 0; i < n; i++) {
        if (ideg[i]) {
            continue;
        }
        ord.clear();
        dfs(i);
        rep[comp_id] = i;
        comps[comp_id] = ord;
        for (auto& a : ord) {
            comp[a] = comp_id;
        }
        comp_id++;
    }

    if (has_cyc) {
        cout << "NO" << endl;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            cout << "NO" << endl;
            return;
        }
    }

    set<int> igraph2[n];
    for (auto& [u, v] : edges2) {
        igraph2[v].insert(u);
    }

    vector<pair<int, int>> cc_e;
    for (int i = 0; i < comp_id; i++) {
        map<int, int> adj_comps;
        for (auto& v : igraph2[rep[i]]) {
            adj_comps[comp[v]]++;
        }

        for (auto& [k, v] : adj_comps) {
            if (v == sz(comps[k])) {
                cc_e.emplace_back(k, i);
            }
        }
    }

    auto comp_ans = Solver(comp_id, cc_e).dfs_tree;
    if (sz(comp_ans) != comp_id - 1) {
        cout << "NO" << endl;
        return;
    }

    vector<pair<int, int>> ans = edges1;
    for (auto& [u, v] : comp_ans) {
        dbg(u, v);
        for (auto& a : comps[u]) {
            if (!igraph2[rep[v]].count(a)) {
                ans.emplace_back(a, rep[v]);
                break;
            }
        }
    }

    for (auto& [u, v] : ans) {
        cout << v << " " << u << endl;
    }
    cout.flush();

    assert(sz(ans) == n - 1);
    {
        set<pair<int, int>> s_ans(begin(ans), end(ans));
        for (auto& e : edges2) {
            assert(!s_ans.count(e));
        }
    }
    Checker _(ans);
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}