Submission #1158235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158235		vladilius	Robot (JOI21_ho_t4)	C++20	100 / 100	1567 ms	132700 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
const ll inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m; cin>>n>>m;
    vector<arr3> g[n + 1];
    map<int, ll> mp[n + 1];
    for (int tt = 1; tt <= m; tt++){
        int x, y, c, w; cin>>x>>y>>c>>w;
        g[x].pb({y, c, w});
        g[y].pb({x, c, w});
        mp[x][c] += w; mp[y][c] += w;
    }
    
    vector<vector<pil>> G = {{}};
    map<pii, int> nd;
    int cc = 0;
    
    auto nw = [&](int x, int y){
        if (nd.find({x, y}) == nd.end()){
            nd[{x, y}] = ++cc;
            G.pb({});
        }
    };

    set<pii> st[m + 1];
    for (int i = 1; i <= n; i++){
        nw(i, 0);
        for (auto [u, c, w]: g[i]){
            nw(u, i);
            G[nd[{i, 0}]].pb({nd[{u, i}], w});
            nw(u, 0);
            G[nd[{i, 0}]].pb({nd[{u, 0}], mp[i][c] - w});
        }
        
        for (auto [u, c, w]: g[i]){
            st[c].insert({w, u});
        }
        
        for (auto [u, c, w]: g[i]){
            nw(i, u);
            G[nd[{i, u}]].pb({nd[{i, 0}], 0});
            
            st[c].erase({w, u});
            if (!st[c].empty()){
                auto [W, T] = *prev(st[c].end());
                G[nd[{i, u}]].pb({nd[{T, 0}], mp[i][c] - w - W});
            }
            st[c].insert({w, u});
        }
        
        for (auto [u, c, w]: g[i]){
            st[c].clear();
        }
    }

    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({0, 1});
    vector<ll> dist(cc + 1, inf); dist[1] = 0;
    while (!pq.empty()){
        auto [d, v] = pq.top(); pq.pop();
        if (d != dist[v]) continue;
        for (auto [u, w]: G[v]){
            ll f = d + w;
            if (f < dist[u]){
                dist[u] = f;
                pq.push({f, u});
            }
        }
    }
    
    ll out = inf;
    for (auto [p, y]: nd){
        if (p.ff == n){
            out = min(out, dist[y]);
        }
    }
    cout<<((out == inf) ? -1 : out)<<"\n";
}

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