Submission #1286094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286094		Faisal_Saqib	Robot (JOI21_ho_t4)	C++20	0 / 100	222 ms	28468 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
const int N=2e5+100;
int a[N],b[N],c[N],p[N];
vector<pair<int,int>> ma[N];
vector<ll> dp[N];
map<int,ll> sm[N];
bool vis[N];
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i]>>c[i]>>p[i];
        ma[a[i]].push_back({c[i],i});
        ma[b[i]].push_back({c[i],i});
    }
    for(int i=1;i<=n;i++)
    {
        sort(begin(ma[i]),end(ma[i]));
        dp[i].resize(ma[i].size()+2,1e18);
        for(auto tlx:ma[i])
        {
            sm[i][tlx.first]+=p[tlx.second];
            // if(i==5)
            // {
            //     cout<<"For five "<<tlx.first<<' '<<tlx.second<<' '<<p[tlx.second]<<' '<<sm[i][tlx.first]<<endl;
            // }
            // if(i==7)
            // {
            //     cout<<"For seven "<<tlx.first<<' '<<tlx.second<<' '<<p[tlx.second]<<' '<<sm[i][tlx.first]<<endl;

            // }
        }
    }
    priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>>pq;
    for(auto tlx:ma[1])
    {
        int c=tlx.first,id=tlx.second;
        int oth=a[id]+b[id]-1,idp=lower_bound(begin(ma[oth]),end(ma[oth]),tlx)-begin(ma[oth]);
        dp[oth][idp]=min(dp[oth][idp],min(sm[1][c]+sm[oth][c]-2*p[id],p[id])); // change this edge or change all other with same color
        pq.push({dp[oth][idp],oth,idp});
    }
    // cout<<"DEG "<<ma[5].size()<<endl;
    while(pq.size()>0)
    {
        auto it=pq.top();
        pq.pop();
        int x=it[1],j=it[2],dt=it[0];
        if(dt!=dp[x][j])
        {
            continue;
        }
    //     // O(M)
    //     // last used 
        int uid=ma[x][j].second,col=ma[x][j].first;
        for(int tlx=0;tlx<ma[x].size();tlx++)
        {
            if(tlx==j)continue;
            int c=ma[x][tlx].first,id=ma[x][tlx].second;
            int oth=a[id]+b[id]-x,idp=lower_bound(begin(ma[oth]),end(ma[oth]),ma[x][tlx])-begin(ma[oth]);
            // if oth==n there is a little bit change in the update
            bool ed=(oth==n);
            int f=1;
            auto txp=lower_bound(begin(ma[oth]),end(ma[oth]),ma[x][j]);
            if(txp!=end(ma[oth]) and (*txp)==ma[x][j])f++;
            int nc=min(sm[x][c]+sm[oth][c]-2*p[id]-f*p[uid]*(col==c),p[id])+dt;
            // if(ed)
            // {
            //     cout<<"From "<<x<<' '<<j<<' '<<dt<<" bef "<<nc<<" af ";
            //     nc=min(nc,dt+min(sm[x][c]-p[id]-p[uid]*(col==c),p[id]));
            //     cout<<nc<<endl;
            // }
            // cout<<"From "<<x<<' '<<j<<' '<<dt<<" To "<<oth<<' '<<idp<<' '<<nc<<endl;
            if(nc<dp[oth][idp])
            {
                // if(nc<=0)
                // {
                //     cout<<"Hola "<<x<<' '<<j<<' '<<dt<<endl;
                //     // cout<<c<<' '<<id<<' '<<oth<<' '<<idp<<' '<<f<<' '<<nc<<endl;
                //     // cout<<ma[oth].size()<<' '<<ma[oth][idp].first<<' '<<ma[oth][idp].second<<endl;;
                //     cout<<sm[x][c]<<' '<<sm[oth][c]<<endl;
                //     cout<<id<<' '<<p[id]<<' '<<uid<<' '<<p[uid]<<' '<<col<<' '<<c<<endl;;
                //     return 0;
                // }
                dp[oth][idp]=nc; // change this edge or change all other with same color
                pq.push({nc,oth,idp});
            }
        }
    }
    // start from n and take edge only if count of that color from the other side of edge is one
    queue<int> q;
    ll ans=1e18;
    q.push(n);
    while(q.size())
    {
        int x=q.front();
        vis[x]=1;
        q.pop();
        for(int j=0;j<ma[x].size();j++)ans=min(ans,dp[x][j]);
         for(int tlx=0;tlx<ma[x].size();tlx++)
        {
            int c=ma[x][tlx].first,id=ma[x][tlx].second;
            int oth=a[id]+b[id]-x;
            // int cnp=0;
            pair<int,int> ftp,stp;
            ftp.first=c;
            ftp.second=m;
            stp.first=c;
            stp.second=1;
            int cnp=upper_bound(begin(ma[oth]),end(ma[oth]),ftp)-lower_bound(begin(ma[oth]),end(ma[oth]),stp);
            if(cnp==1 and !vis[oth])
            {  
                vis[oth]=1;
                q.push(oth);
            }
        }
    }
    if(ans==1e18)ans=-1;
    cout<<ans<<endl;
}

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