Submission #416054

#	Time	Username	Problem	Language	Result	Execution time	Memory
416054		meatrow	Robot (JOI21_ho_t4)	C++17	100 / 100	1397 ms	86380 KiB

Main

// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
 
const int MOD = 1e9 + 7;
 
ll binpow(ll a, ll p, int mod = MOD) {
    ll res = 1;
    while (p) {
        if (p & 1) {
            (res *= a) %= mod;
        }
        p >>= 1;
        (a *= a) %= mod;
    }
    return res;
}
 
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
 
struct Edge {
    int a, b, color, price;
};
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    vector<vector<int>> g(n + 1), col(n + 1);
    vector<map<int, int>> rev(n + 1), start(n + 1), end(n + 1);

    for (int i = 0; i < m; i++) {
        cin >> edges[i].a >> edges[i].b >> edges[i].color >> edges[i].price;
        g[edges[i].a].push_back(i);
        g[edges[i].b].push_back(i);
    }

    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end(), [&](int a, int b) {
            return edges[a].color < edges[b].color;
        });
        for (int j = 0; j < g[i].size(); j++) {
            int c = edges[g[i][j]].color;
            if (!start[i].count(c)) {
                start[i][c] = j;
            }
            end[i][c] = j;
            if (col[i].empty() || c != col[i].back()) {
                rev[i][c] = col[i].size();
                col[i].push_back(c);
            }
        }
    }
    
    vector<vector<ll>> dist(n + 1);
    for (int i = 1; i <= n; i++) {
        dist[i].assign(col[i].size() + 1, 1e18);
    }
    dist[1][col[1].size()] = 0;
    set<pair<ll, pair<int, int>>> setik;
    setik.insert({0, {1, col[1].size()}});
    ll ans = 1e18;
    while (!setik.empty()) {
        int v, from;
        tie(v, from) = setik.begin()->second;
        if (v == n && from == col[n].size()) {
            ans = min(ans, dist[v][from]);
        }
        setik.erase(setik.begin());

        if (from == col[v].size()) {
            map<int, ll> sum;
            for (int i = 0; i < g[v].size(); i++) {
                auto& edge = edges[g[v][i]];
                sum[edge.color] += edge.price;
            }
            for (int i = 0; i < g[v].size(); i++) {
                auto& edge = edges[g[v][i]];
                int to = edge.a ^ edge.b ^ v;
                ll w = 0;
                int id = rev[to][edge.color];
                if (dist[v][from] + w < dist[to][id]) {
                    setik.erase({dist[to][id], {to, id}});
                    dist[to][id] = dist[v][from] + w;
                    setik.insert({dist[to][id], {to, id}});
                }
                w = min<ll>(edge.price, sum[edge.color] - edge.price);
                id = col[to].size();
                if (dist[v][from] + w < dist[to][id]) {
                    setik.erase({dist[to][id], {to, id}});
                    dist[to][id] = dist[v][from] + w;
                    setik.insert({dist[to][id], {to, id}});
                }
            }
            continue;
        }

        // color has changed
        int color = col[v][from];
        ll sum = 0;
        for (int i = start[v][color]; i <= end[v][color]; i++) {
            sum += edges[g[v][i]].price;
        }
        for (int i = start[v][color]; i <= end[v][color]; i++) {
            auto& edge = edges[g[v][i]];
            int to = edge.a ^ edge.b ^ v;
            ll w = sum - edge.price;
            int id = col[to].size();
            if (dist[v][from] + w < dist[to][id]) {
                setik.erase({dist[to][id], {to, id}});
                dist[to][id] = dist[v][from] + w;
                setik.insert({dist[to][id], {to, id}});
            }
        }
    }
 
    if (ans == 1e18) ans = -1;
    cout << ans << '\n';
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int j = 0; j < g[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~
Main.cpp:73:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         if (v == n && from == col[n].size()) {
      |                       ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         if (from == col[v].size()) {
      |             ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:80:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             for (int i = 0; i < g[v].size(); i++) {
      |                             ~~^~~~~~~~~~~~~
Main.cpp:84:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             for (int i = 0; i < g[v].size(); i++) {
      |                             ~~^~~~~~~~~~~~~

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