Submission #1272619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272619		witek_cpp	Robot (JOI21_ho_t4)	C++20	0 / 100	82 ms	18480 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = (ll)9e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n+1);
    // edge: (a,b), color c, cost p
    vector<pair<pair<int,int>, pair<int,ll>>> e(m+1);
    vector<unordered_map<int,int>> ile(n+1);
    vector<unordered_map<int,ll>> suma(n+1);

    for (int i = 1; i <= m; ++i) {
        int a,b,c; ll p;
        cin >> a >> b >> c >> p;
        e[i] = {{a,b},{c,p}};
        g[a].push_back(i);
        g[b].push_back(i);
        ile[a][c]++; ile[b][c]++;
        suma[a][c] += p; suma[b][c] += p;
    }

    // dist for being at node v with "no incoming edge" (ind == 0)
    vector<ll> distNode(n+1, INF);
    // dist for state "we arrived to some node through edge ind"
    vector<ll> distEdge(m+1, INF);

    // priority queue of tuples: (cost, node v, incoming_edge ind)
    // we'll store negative cost to get min-heap behavior with pair
    using T = tuple<ll,int,int>;
    priority_queue<T> pq;
    distNode[1] = 0;
    pq.push({0, 1, 0}); // cost 0, at node 1, incoming edge 0

    auto kr = [&](int v, int ind) -> pair<int, pair<int,ll>> {
        // returns {other_vertex, {color, p}}
        if (e[ind].first.first == v) return {e[ind].first.second, e[ind].second};
        else return {e[ind].first.first, e[ind].second};
    };

    while (!pq.empty()) {
        auto [negcost, v, ind] = pq.top(); pq.pop();
        ll cost = -negcost;

        // check whether this tuple matches current best dist
        if (ind == 0) {
            if (cost != distNode[v]) continue;
        } else {
            if (cost != distEdge[ind]) continue;
        }

        // if we reached node n in node-state (ind==0), answer found
        if (v == n && ind == 0) {
            cout << cost << '\n';
            return 0;
        }

        // precompute incoming color and p if ind != 0
        int incoming_color = -1; ll incoming_p = 0;
        if (ind != 0) {
            auto tmp = kr(v, ind);
            incoming_color = tmp.second.first;
            incoming_p = tmp.second.second;
        }

        // explore all incident edges from v
        for (int edge_id : g[v]) {
            auto u = kr(v, edge_id);
            int to = u.first;
            int color = u.second.first;
            ll p = u.second.second;

            // read cnt and sum_total WITHOUT operator[] (use find)
            int cnt = 0;
            auto itc = ile[v].find(color);
            if (itc != ile[v].end()) cnt = itc->second;
            ll sum_total = 0;
            auto its = suma[v].find(color);
            if (its != suma[v].end()) sum_total = its->second;

            // if incoming has same color, exclude it from counts (local, no writes)
            if (ind != 0 && incoming_color == color) {
                cnt -= 1;
                sum_total -= incoming_p;
            }

            if (cnt == 1) {
                // unique color -> can go to 'to' as node-state with same cost
                if (cost < distNode[to]) {
                    distNode[to] = cost;
                    pq.push({-cost, to, 0});
                }
            } else {
                // option 1: go to 'to' with incoming edge state (we traversed edge edge_id),
                // cost increases by p (recolor this edge to unique color)
                ll newCostEdge = cost + p;
                if (newCostEdge < distEdge[edge_id]) {
                    distEdge[edge_id] = newCostEdge;
                    pq.push({-newCostEdge, to, edge_id});
                }

                // option 2: recolor *other* edges of this color at v so that this edge becomes unique
                // cost to recolor others = sum_total - p
                if (p > (sum_total - p)) {
                    ll alt = cost + (sum_total - p);
                    if (alt < distNode[to]) {
                        distNode[to] = alt;
                        pq.push({-alt, to, 0});
                    }
                }
            }
        }
    }

    // if queue exhausted and no distNode[n] found
    if (distNode[n] == INF) cout << -1 << '\n';
    else cout << distNode[n] << '\n';
    return 0;
}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42