Submission #1286104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286104		Faisal_Saqib	Robot (JOI21_ho_t4)	C++20	0 / 100	3098 ms	71868 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][2];
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][0].resize(ma[i].size()+2,1e18);
        dp[i][1].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(int i=0;i<ma[1].size();i++)
    {
        dp[1][0][i]=0;
        pq.push({0,1,0,i});
    }
    while(pq.size()>0)
    {
        auto it=pq.top();
        pq.pop();
        int x=it[1],j=it[3],dt=it[0],chg=it[2];
        if(dt!=dp[x][chg][j])
        {
            continue;
        }
    //     // O(M)
    //     // last used 
        int uid=ma[x][j].second,col=ma[x][j].first;
        if(chg)
        {
            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]);
                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(nc<dp[oth][1][idp])
                {
                    dp[oth][1][idp]=nc; // change this edge or change all other with same color
                    pq.push({nc,oth,1,idp});
                }
                nc=min(sm[x][c]-p[id]-p[uid]*(col==c),p[id])+dt;
                if(nc<dp[oth][0][idp])
                {
                    dp[oth][0][idp]=nc; // change this edge or change all other with same color
                    pq.push({nc,oth,0,idp});
                }
                pair<int,int> ftp,stp;
                ftp.first=c;
                ftp.second=m;
                stp.first=c;
                stp.second=1;
                int cnp=upper_bound(begin(ma[x]),end(ma[x]),ftp)-lower_bound(begin(ma[x]),end(ma[x]),stp);
                nc=dt;
                if((cnp==1 or (cnp==2 and c==col)) and nc<dp[oth][0][idp])
                {
                    dp[oth][0][idp]=nc;
                    pq.push({nc,oth,0,idp});
                }
            }
        }
            else{
                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]);
                    int nc=min(sm[x][c]+sm[oth][c]-2*p[id],p[id])+dt;
                    if(nc<dp[oth][1][idp])
                    {
                        dp[oth][1][idp]=nc; // change this edge or change all other with same color
                        pq.push({nc,oth,1,idp});
                    }
                    nc=min(sm[x][c]-p[id],p[id])+dt;
                    if(nc<dp[oth][0][idp])
                    {
                        dp[oth][0][idp]=nc; // change this edge or change all other with same color
                        pq.push({nc,oth,0,idp});
                    }
                    pair<int,int> ftp,stp;
                    ftp.first=c;
                    ftp.second=m;
                    stp.first=c;
                    stp.second=1;
                    int cnp=upper_bound(begin(ma[x]),end(ma[x]),ftp)-lower_bound(begin(ma[x]),end(ma[x]),stp);
                    nc=dt;
                    if(cnp==1 and nc<dp[oth][0][idp])
                    {
                        dp[oth][0][idp]=nc;
                        pq.push({nc,oth,0,idp});
                    }
                }
            // }
        }
    }
    ll ans=1e18;
    for(int j=0;j<ma[n].size();j++)ans=min(ans,dp[n][0][j]);
    for(int j=0;j<ma[n].size();j++)ans=min(ans,dp[n][1][j]);
    if(ans==1e18)ans=-1;
    cout<<ans<<endl;
}

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