Submission #1157745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157745		ReLice	Robot (JOI21_ho_t4)	C++20	100 / 100	367 ms	54148 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld double
#define pb push_back
#define pf push_front
#define ins insert
#define fr first
#define sc second
#define endl "\n"
#define ar array
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
void start(){ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);}

const ll inf = 1e17;
const ll mod = 1e9 + 7;
const ll N = 1e5 + 8;

vector<vector<vector<pair<ll,ll>>>> g(N);
vector<vector<ll>> vv(N), sum(N), mn(N);

ll d[N];
bool vis[N];

void bfs(ll v){
    // all except y of the same color, mn[col[y]], price[y]

    memset(d, 0x3f, sizeof(d));
    set<pair<ll,ll>> q;

    d[v] = 0;
    q.ins({0, v});

    while(!q.empty()){
        auto [dd, x] = *q.begin();
        vis[x] = 1;

        q.erase(q.begin());

        if(dd != d[x]) continue;

        for(ll i=0;i<(ll)vv[x].size();i++){

            for(auto [p, to] : g[x][i]){
                if(vis[to]) continue;

                ll res = min(d[x] + min(p, sum[x][i] - p), mn[x][i] - p);

                if(res < d[to]){
                    d[to] = res;
                    q.ins({d[to], to});
                }

                ll col = lower_bound(all(vv[to]), vv[x][i]) - vv[to].begin();

                if(d[x] + p + sum[to][col] - p < mn[to][col]){
                    mn[to][col] = d[x] + p + sum[to][col] - p;
                }
            }
        }

    }
}

void solve() {
    ll i, j;

    ll n, m;
    cin>>n>>m;

    ll a[m], b[m], c[m], dd[m];

    for(i=0;i<m;i++){
        cin>>a[i]>>b[i]>>c[i]>>dd[i];

        vv[a[i]].pb(c[i]);
        vv[b[i]].pb(c[i]);
    }

    for(i=1;i<=n;i++){
        sort(all(vv[i]));
        vv[i].erase(unique(all(vv[i])), vv[i].end());

        g[i].resize(vv[i].size());
        sum[i].resize(vv[i].size());
        mn[i].resize(vv[i].size(), inf);
    }

    for(i=0;i<m;i++){
        ll low = lower_bound(all(vv[a[i]]), c[i]) - vv[a[i]].begin();
        g[a[i]][low].pb({dd[i], b[i]});
        sum[a[i]][low] += dd[i];

        low = lower_bound(all(vv[b[i]]), c[i]) - vv[b[i]].begin();
        g[b[i]][low].pb({dd[i], a[i]});
        sum[b[i]][low] += dd[i];
    }

    bfs(1);

    if(d[n] >= d[0]) cout<<-1<<endl;
    else cout<<d[n]<<endl;
}

signed main(){
    start();

    ll t = 1;
    //cin>>t;

    while(t--) solve();
}

/*

*/

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