← Real problems

sdoi17r2p4

unratedStatement on DMOJ

CP Lang

44 lines0.3 spec
// SDOI 2017 "Dictionary Trie Road Network": entering road b after road a costs
// w(b) plus the depth of the LCA of their words in a trie; shortest paths from 1
// over roads. At a vertex, sort the roads entering and leaving it by their
// words' trie preorder: the LCA depth of two words is the minimum over the
// adjacent pairs between them, so two prefix chains and a cross arc per gap
// (one pass each way) carry every turn in O(deg) arcs instead of O(deg^2).
@!multitest
let (n, m, k) = read<(1..=5e4, 1..=1e5, 1..=2e4)>()
domain V = 1..=n
domain Word = 1..=k
domain Road = [m]
let roads = read<[Road](u: V, v: V, w: 1..=2e4, word: Word)>()
let trie = Rooted(Graph.undirected(read<[k - 1](u: Word, v: Word, c: Int)>()), root: Word.first!)
let lca = LcaTable(trie)
let leave = Graph.directed(roads)
let enter = leave.transpose()

domain Aux = [8 * m]
domain Node = Road + Aux
var arcs = List<(from: Node, arc: (to: Node, w: Int))>()
var used = 0
for x in V:
    let here = List(chain(
        enter.out(x).map(a => (road: a.e, enters: true)),
        leave.out(x).map(a => (road: a.e, enters: false)),
    )).sorted(by: it => trie.pos(roads[it.road].word))
    for line in [here, List(here.rev)]:
        let t = line.len
        let (pre, suf) = ((i: Int) => Node(Aux(used + i)), (i: Int) => Node(Aux(used + t + i)))
        for (i, it) in line.items:
            if it.enters:
                arcs.push((from: Node(it.road), arc: (to: pre(i), w: 0)))
            else:
                arcs.push((from: suf(i), arc: (to: Node(it.road), w: roads[it.road].w)))
            if i + 1 < t:
                let gap = trie.depth(lca.lca(roads[it.road].word, roads[line[i + 1].road].word))
                arcs.push((from: pre(i), arc: (to: pre(i + 1), w: 0)))
                arcs.push((from: suf(i), arc: (to: suf(i + 1), w: 0)))
                arcs.push((from: pre(i), arc: (to: suf(i + 1), w: gap)))
        used += 2 * t

let dist = dijkstra(Graph.of(arcs), from: leave.out(V.first!).map(a => (Node(a.e), roads[a.e].w))).dist
for v in V.drop(1):
    print(enter.out(v).filter_map(a => dist[Node(a.e)]).min()!)

Accepted C++

298 lines · 11.00 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

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

#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))

template <typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

template <typename T>
struct ST {
    int n;
    vector<vector<T>> v;

    ST() {}
    ST(const vector<T>& arr) : n(sz(arr)), v(__lg(n) + 1, vector<T>(n)) {
        v[0] = arr;
        for (int i = 1; i <= __lg(n); i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                v[i][j] = min(v[i - 1][j], v[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    T query(int l, int r) const {
        int x = __lg(r - l);
        return min(v[x][l], v[x][r - (1 << x)]);
    }
};

template <typename Cb>
struct KeyCmp {
    Cb cb;

    KeyCmp(Cb cb) : cb(cb) {}

    template <typename T>
    bool operator()(const T& a, const T& b) const {
        return cb(a) < cb(b);
    }
};

struct Dijkstra {
    vector<vector<pair<int, long>>> graph;

    Dijkstra() {}

    int new_node() {
        graph.emplace_back();
        return sz(graph) - 1;
    }

    vector<int> new_node(int n) {
        vector<int> arr;
        for (int i = 0; i < n; i++) {
            arr.push_back(new_node());
        }
        return arr;
    }

    void add_edge(int u, int v, long w) {
        graph[u].emplace_back(v, w);
    }

    vector<long> query(int src) const {
        vector<long> dist(sz(graph), 1e18);
        min_pq<pair<long, int>> pq;
        auto push = [&](int u, long d) -> void {
            if (d >= dist[u]) {
                return;
            }
            dist[u] = d;
            pq.emplace(d, u);
        };
        push(src, 0);
        while (sz(pq)) {
            auto [d, u] = pq.top();
            pq.pop();
            if (dist[u] != d) {
                continue;
            }
            for (auto& [v, w] : graph[u]) {
                push(v, d + w);
            }
        }
        return dist;
    }
};

struct Tree {
    int n;
    vector<int> depth, tin, tout, ord;
    vector<vector<int>> graph;
    ST<int> st_ord;

    Tree(int n, int root, const vector<pair<int, int>>& edges)
        : n(n), depth(n), tin(n), tout(n), graph(n) {
        for (auto& [u, v] : edges) {
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        dfs(root, -1, 0);
        vector<int> stv;
        for (auto& a : ord) {
            stv.push_back(tin[a]);
        }
        st_ord = stv;
    }

    int lca(int u, int v) const {
        if (tin[u] > tin[v]) {
            swap(u, v);
        }
        return ord[st_ord.query(tin[u], tout[v])];
    }

    pair<vector<int>, vector<pair<int, int>>> virtual_tree(vector<int> nodes) {
        sort(begin(nodes), end(nodes),
             KeyCmp([&](int u) -> int { return tin[u]; }));
        vector<int> anodes = nodes;
        for (int i = 0; i < sz(nodes) - 1; i++) {
            anodes.push_back(lca(nodes[i], nodes[i + 1]));
        }
        sort(begin(anodes), end(anodes),
             KeyCmp([&](int u) -> int { return tin[u]; }));
        anodes.erase(unique(begin(anodes), end(anodes)), anodes.end());
        vector<int> st;
        vector<pair<int, int>> edges;
        for (auto& a : anodes) {
            while (sz(st) && tout[st.back()] <= tin[a]) {
                st.pop_back();
            }
            if (sz(st)) {
                edges.emplace_back(st.back(), a);
            }
            st.push_back(a);
        }
        return {anodes, edges};
    }

    void dfs(int u, int p, int d) {
        tin[u] = sz(ord);
        depth[u] = d;
        ord.push_back(u);
        for (auto& v : graph[u]) {
            if (v == p) {
                continue;
            }
            dfs(v, u, d + 1);
            ord.push_back(u);
        }
        tout[u] = sz(ord);
    }
};

constexpr int maxn = 5e4 + 5;

// nodes - (u, depth, in, out)
// edges - (par, child)
void construct_tree(Dijkstra& graph,
                    vector<array<int, 4>> nodes,
                    vector<pair<int, int>> edges) {
    static int nmap[maxn];
    int n = sz(nodes);
    for (int i = 0; i < n; i++) {
        nmap[nodes[i][0]] = i;
    }
    vector<int> tup = graph.new_node(n), tdown = graph.new_node(n);
    for (auto& [u, v] : edges) {
        graph.add_edge(tup[nmap[v]], tup[nmap[u]], 0);
        graph.add_edge(tdown[nmap[u]], tdown[nmap[v]], 0);
    }
    for (int i = 0; i < n; i++) {
        graph.add_edge(nodes[i][2], tup[i], 0);
        graph.add_edge(tdown[i], nodes[i][3], 0);
    }
    for (int i = 0; i < n; i++) {
        graph.add_edge(nodes[i][2], tdown[i], nodes[i][1]);
        graph.add_edge(tup[i], nodes[i][3], nodes[i][1]);
    }
    map<int, vector<int>> mch;
    for (auto& [u, v] : edges) {
        mch[u].push_back(v);
    }
    for (auto& [u, ch] : mch) {
        int m = sz(ch);
        vector<int> pref = graph.new_node(m), suff = graph.new_node(m);
        for (int i = 0; i < m; i++) {
            graph.add_edge(pref[i], tdown[nmap[ch[i]]], 0);
            graph.add_edge(suff[i], tdown[nmap[ch[i]]], 0);
        }
        for (int i = 0; i < m - 1; i++) {
            graph.add_edge(pref[i + 1], pref[i], 0);
            graph.add_edge(suff[i], suff[i + 1], 0);
        }
        for (int i = 0; i < m; i++) {
            if (i) {
                graph.add_edge(tup[nmap[ch[i]]], pref[i - 1],
                               nodes[nmap[u]][1]);
            }
            if (i + 1 < m) {
                graph.add_edge(tup[nmap[ch[i]]], suff[i + 1],
                               nodes[nmap[u]][1]);
            }
        }
    }
}

void solve() {
    int n, m, kv;
    cin >> n >> m >> kv;
    int edges[m][4];
    for (auto& [u, v, w, t] : edges) {
        cin >> u >> v >> w >> t;
        u--;
        v--;
        t--;
    }
    vector<pair<int, int>> trie_edges(kv - 1);
    for (auto& [u, v] : trie_edges) {
        int _w;
        cin >> u >> v >> _w;
        u--;
        v--;
    }
    Tree trie(kv, 0, trie_edges);
    Dijkstra graph;
    vector<int> reqs[n];
    map<int, int> nodes[n][2];
    for (auto& [u, v, w, t] : edges) {
        reqs[u].push_back(t);
        reqs[v].push_back(t);
    }
    for (int i = 0; i < n; i++) {
        auto [anodes, tedges] = trie.virtual_tree(reqs[i]);
        vector<array<int, 4>> cnodes;
        for (auto& a : anodes) {
            cnodes.push_back({a, trie.depth[a],
                              nodes[i][0][a] = graph.new_node(),
                              nodes[i][1][a] = graph.new_node()});
        }
        construct_tree(graph, cnodes, tedges);
    }
    for (auto& [u, v, w, t] : edges) {
        graph.add_edge(nodes[u][1][t], nodes[v][0][t], w);
    }
    int src = graph.new_node();
    for (auto& [_k, v] : nodes[0][1]) {
        graph.add_edge(src, v, 0);
    }
    vector<long> dist = graph.query(src);
    long ans[n];
    memset(ans, 0x3f, sizeof(ans));
    for (int i = 0; i < n; i++) {
        for (auto& [_k, v] : nodes[i][0]) {
            ans[i] = min(ans[i], dist[v]);
        }
    }
    for (int i = 1; i < n; i++) {
        cout << ans[i] << endl;
    }
}

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