Submission #1155755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155755		dnnnda	Robot (JOI21_ho_t4)	C++20	34 / 100	3096 ms	47368 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
const int X=1000000007;

vector<array<int,4>> adj[100005];
vector<pair<int,ll>> cost[100005];
priority_queue<array<ll,4>,vector<array<ll,4>>,greater<array<ll,4>>> pq;
ll len[800010], ans=inff, nlen[800010];
int col[400005];
void add(int u, int c, int pr){
    auto iter=lower_bound(cost[u].begin(),cost[u].end(),make_pair(c,0LL));
    (*iter).S+=pr;
}
ll ask(int u, int c){
    auto iter=lower_bound(cost[u].begin(),cost[u].end(),make_pair(c,0LL));
    return (*iter).S;
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    memset(len,0x3f,sizeof len);
    memset(nlen,0x3f,sizeof nlen);
    int n, m; cin >> n >> m;
    queue<array<int,4>> q;
    for(int i=1 ; i<=m ; i++){
        int a, b, c, p; cin >> a >> b >> c >> p;
        adj[a].push_back({b,c,p,i<<1});
        adj[b].push_back({a,c,p,i<<1|1});
        cost[a].push_back({c,0});
        cost[b].push_back({c,0});
        col[i<<1]=c;
        col[i<<1|1]=c;
        q.push({a,b,c,p});
    }
    for(int i=1 ; i<=n ; i++) sort(cost[i].begin(),cost[i].end());
    while(!q.empty()){
        auto[a,b,c,p]=q.front();
        q.pop();
        add(a,c,p);
        add(b,c,p);
    }

    len[1]=0;
    nlen[1]=0;
    pq.push({0,1,1,0}); //length, node, edge, paid?
    while(!pq.empty()){
        auto[l,u,e,pd]=pq.top();
        pq.pop();
        if(len[e*2+(pd>0)]<l) continue;
        if(pd==0&&nlen[u]<l) continue;
        if(u==n) ans=min(ans,l);
        for(auto[v,c,p,i]:adj[u]){
            ll f=ask(u,c)-(col[e]==c ? pd : 0LL);
            if(l+p<len[i<<1|1]){
                len[i<<1|1]=l+p;
                pq.push({l+p,v,i,p});
            }
            if(l+(f-p)<len[i<<1]&&l+(f-p)<nlen[v]){
                len[i<<1]=l+(f-p);
                nlen[v]=l+(f-p);
                pq.push({l+(f-p),v,i,0});
            }
        }
    }
    cout << (ans==inff ? -1LL : ans) << '\n';

    return 0;
}

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