Submission #1215763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215763		sitablechair	Robot (JOI21_ho_t4)	C++20	100 / 100	1331 ms	57528 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=2e5+3;

struct bst {
    int lb,lsb,rb,rsb;
    ll ls,rs;
};

struct item {
    ll w;
    int u,idx;
    bool operator < (const item oth) const {
        return w>oth.w;
    }
};

struct edge {
    int u,v,w,c;
};

map<pair<int,int>,ll> d;
map<ll,int> b,sb;
map<ll,ll> sm;
int n,m;
edge e[N];
vector<int> g[N];
bst bb[N];
priority_queue<item> pq;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    For(i,1,m) {
        cin >> e[i].u >> e[i].v >> e[i].c >> e[i].w;
        g[e[i].u].pb(i);
        g[e[i].v].pb(i);
    }
    For(i,1,n) {
        b.clear(),sb.clear(),sm.clear();
        for(auto el: g[i]) {
            sm[e[el].c]+=e[el].w;
            if (!b.count(e[el].c)) b[e[el].c]=el;
            else {
                if (e[b[e[el].c]].w<e[el].w) {
                    sb[e[el].c]=b[e[el].c];
                    b[e[el].c]=el;
                } else if (!sb.count(e[el].c) || e[sb[e[el].c]].w<e[el].w) {
                    sb[e[el].c]=el;
                }
            }
        }
        for(auto el: g[i]) {
            // if (i==3) debug(b[4]);
            if (e[el].u==i) {
                bb[el].lb=b[e[el].c];
                bb[el].lsb=sb[e[el].c];
                bb[el].ls=sm[e[el].c];
            } else {
                bb[el].rb=b[e[el].c];
                bb[el].rsb=sb[e[el].c];
                bb[el].rs=sm[e[el].c];
            }
        }
    }
    pq.push({0,1,-1});
    d[{1,-1}]=0;
    // debug(bb[3].rb);
    while(sz(pq)) {
        ll w=pq.top().w;
        int u=pq.top().u,idx=pq.top().idx;
        pq.pop();
        // debug(w,u,idx);
        if (d[{u,idx}]!=w) continue;
        if (idx==-1) {
            for(auto i: g[u]) {
                int v=(e[i].u==u?e[i].v:e[i].u);
                if (!d.count({v,i}) || d[{v,i}]>w+e[i].w) {
                    d[{v,i}]=e[i].w+w;
                    pq.push({e[i].w+w,v,i});
                }
                ll ww=0;
                if (e[i].u==u) ww=bb[i].ls-e[i].w;
                else ww=bb[i].rs-e[i].w;
                if (!d.count({v,-1}) || d[{v,-1}]>ww+w) {
                    d[{v,-1}]=w+ww;
                    pq.push({w+ww,v,-1});
                }
            }
        } else {
            if (!d.count({u,-1}) || d[{u,-1}]>w) {
                d[{u,-1}]=w;
                pq.push({w,u,-1});
            }
            int s1,s2;
            if (e[idx].u==u) {
                s1=bb[idx].lb;
                s2=bb[idx].lsb;
            } else {
                s1=bb[idx].rb;
                s2=bb[idx].rsb;
            }
            if (s1!=idx) {
                int v=(e[s1].u==u?e[s1].v:e[s1].u);
                ll ww=(e[s1].u==u?bb[s1].ls:bb[s1].rs);
                ww-=e[idx].w+e[s1].w;
                if (!d.count({v,-1}) || d[{v,-1}] > ww+w) {
                    d[{v,-1}]=ww+w;
                    pq.push({ww+w,v,-1});
                }
            } else if (s2!=0) {
                int v=(e[s2].u==u?e[s2].v:e[s2].u);
                ll ww=(e[s2].u==u?bb[s2].ls:bb[s2].rs);
                ww-=e[idx].w+e[s2].w;
                if (!d.count({v,-1}) || d[{v,-1}] > ww+w) {
                    d[{v,-1}]=ww+w;
                    pq.push({ww+w,v,-1});
                }
            }
        }
    }
    ll ans=1e18;
    for(auto el: d) 
        if (el.ff.ff==n) ans=min(ans,el.ss);
    if (ans>=1e18) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

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