Submission #1249501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249501		nastya_an	Robot (JOI21_ho_t4)	C++20	34 / 100	3099 ms	113076 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define cin(v) \
    for (auto &el : v) { cin >> el; }
#define cout(v)                               \
    for (auto &el : v) { cout << el << " "; } \
    cout << "\n";

using namespace std;
using ll = long long;
using db = double;
using ldb = long double;
const ldb EPS = 1e-9;
const ll LINF = 2e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 1072005019;
const ll MOD3 = 998244353;
const ldb PI = acos(-1.0);

struct edge {
    int to, col, cost;
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<edge>> g(n);
    for (int i = 0; i < m; i++) {
        int v, u, col, cost;
        cin >> v >> u >> col >> cost;
        v--; u--;
        g[v].push_back(edge(u, col, cost));
        g[u].push_back(edge(v, col, cost));
    }
    map<vector<int>, ll> dist;
    set<pair<ll, vector<int>>> s;
    // prev, cur
    s.insert({0, {-1, 0, 0}});
    dist[{-1, 0, 0}] = 0;
    /*vector<map<int, int>> maps;
    vector<map<int, int>> sums;
    for (int cur = 0; cur < m; cur++) {
        for (edge& e : g[cur]) {
            maps[cur][e.col]++;
            sums[cur][e.col] += e.cost;
        }
    }*/
    while (s.size()) {
        auto el = *s.begin();
        s.erase(s.begin());
        ll d = el.first;
        int prev = el.second[0], cur = el.second[1], use = el.second[2];
        unordered_map<int, int> mp;
        unordered_map<int, ll> sum;
        for (edge& e : g[cur]) {
            if (e.to == prev && use) {
                continue;
            }
            mp[e.col]++;
            sum[e.col] += e.cost;
        }
        for (edge& e : g[cur]) {
            if (e.to == prev && use) {
                continue;
            }
            if (mp[e.col] >= 2) {
                if (!dist.contains({cur, e.to, 0}) || dist[{cur, e.to, 0}] > d + sum[e.col] - e.cost) {
                    s.erase({ dist[{cur, e.to, 0}], {cur, e.to, 0}});
                    dist[{cur, e.to, 0}] = d + sum[e.col] - e.cost;
                    s.insert({ dist[{cur, e.to, 0}], {cur, e.to, 0}});
                }
                if (!dist.contains({cur, e.to, 1}) || dist[{cur, e.to, 1}] > d + e.cost) {
                    s.erase({ dist[{cur, e.to, 1}], {cur, e.to, 1}});
                    dist[{cur, e.to, 1}] = d + e.cost;
                    s.insert({ dist[{cur, e.to, 1}], {cur, e.to, 1}});
                }
            } else {
                if (!dist.contains({cur, e.to, 0}) || dist[{cur, e.to, 0}] > d) {
                    s.erase({ dist[{cur, e.to, 0}], {cur, e.to, 0}});
                    dist[{cur, e.to, 0}] = d;
                    s.insert({ dist[{cur, e.to, 0}], {cur, e.to, 0}});
                }
                if (!dist.contains({cur, e.to, 1}) || dist[{cur, e.to, 1}] > d + e.cost) {
                    s.erase({ dist[{cur, e.to, 1}], {cur, e.to, 1}});
                    dist[{cur, e.to, 1}] = d + e.cost;
                    s.insert({ dist[{cur, e.to, 1}], {cur, e.to, 1}});
                }
            }
        }
    }
    ll ans = 1e18;
    for (edge& e : g[n - 1]) {
        if (dist.contains({e.to, n - 1, 0}) && dist[{e.to, n - 1, 0}] < ans) {
            ans = dist[{e.to, n - 1, 0}];
        }
        if (dist.contains({e.to, n - 1, 1}) && dist[{e.to, n - 1, 1}] < ans) {
            ans = dist[{e.to, n - 1, 1}];
        }
    }
    if (ans == 1e18) ans = -1;
    cout << ans << "\n";
    return;
}


signed main() {
    ll interactive = 0;
    ll multitest = 0;
    if (!interactive) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
#ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
#endif
    }
    if (multitest) {
        ll T;
        cin >> T;
        while (T--) {
            solve();
        }
    } else {
        solve();
    }
    return 0;
}

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