Submission #1158923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158923		Marco_Escandon	Robot (JOI21_ho_t4)	C++20	34 / 100	3102 ms	645648 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
typedef long long ll;
#define x first
#define y second
vector<vector<pair<int,int>>> cad;
map<int,vector<pair<int,int>>> cad2[(ll)1e5+5];
vector<map<int,ll>> c2;
vector<pair<int,int>> E;
int n,m;
struct st{
    ll cost;int node,ed;
    friend bool operator < (st a, st b)
    {
        return a.cost>b.cost;
    }
};
ll cmc()
{
    vector<map<int,ll>> v(cad.size()),v2(cad.size());
    priority_queue<st>q;q.push({1,1,m+1});
    while(!q.empty())
    {
        st temp=q.top();q.pop();
        //cerr<<temp.node<<" "<<temp.cost-1<<"\n";
        if(temp.ed==m+1)
        {
            if(v[temp.node][temp.ed]==0)
            {
                if(temp.node==n) return temp.cost-1;
                v[temp.node][temp.ed]=temp.cost;
                for(auto i:cad[temp.node])
                {
                    ll cnt=c2[temp.node][E[i.y].x]-E[i.y].y;
                    if(E[temp.ed].x==E[i.y].x)
                        cnt-=E[temp.ed].y;
                        ll t1=v2[i.x][m+1];
                    if(t1==0||temp.cost+min(cnt,(ll)E[i.y].y)<t1)
                    { 
                        q.push({temp.cost+min(cnt,(ll)E[i.y].y),i.x,m+1});  
                    }
                    t1=v2[i.x][i.y];
                    if(t1==0||temp.cost+E[i.y].y<t1)
                    {
                        q.push({temp.cost+E[i.y].y,i.x,i.y});
                    }
                }
            }
        }
        else if(v[temp.node][temp.ed]==0)
        {
            if(temp.node==n) return temp.cost-1;
            v[temp.node][temp.ed]=temp.cost;
            for(auto i:cad2[temp.node][E[temp.ed].x])
            {
                ll cnt=c2[temp.node][E[i.y].x]-E[i.y].y;
                if(E[temp.ed].x==E[i.y].x)
                    cnt-=E[temp.ed].y;
                ll t1=v2[i.x][m+1];
                if(t1==0||temp.cost+min(cnt,(ll)E[i.y].y)<t1)
                { 
                    q.push({temp.cost+min(cnt,(ll)E[i.y].y),i.x,m+1});  
                }
                t1=v2[i.x][i.y];
                if(t1==0||temp.cost+E[i.y].y<t1)
                {
                    q.push({temp.cost+E[i.y].y,i.x,i.y});
                }
            }
        }
    }
    return 1e16;
}
int main()
{
  
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    cad.resize(n+1);
    c2.resize(n+1);
    E.resize(m+2);
    for(int i=0; i<m; i++)
    {
        int a,b;
        cin>>a>>b>>E[i].x>>E[i].y;
        cad[a].push_back({b,i});
        cad[b].push_back({a,i});
        c2[a][E[i].x]+=E[i].y;
        c2[b][E[i].x]+=E[i].y;
        cad2[a][E[i].x].push_back({b,i});
        cad2[b][E[i].x].push_back({a,i});
    }
    ll t1=cmc();
    if(t1==1e16) t1=-1;
    cout<<t1; 
}

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