Submission #1223201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223201		TadijaSebez	Robot (JOI21_ho_t4)	C++20	100 / 100	1339 ms	105908 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

const int N=100050;
const int M=5*N;
vector<array<int,3>> E[N];
vector<pair<int,ll>> G[M];
void AddEdge(int u,int v,ll w){
    assert(w>=0);
    G[u].pb({v,w});
}
const ll inf=1e18;
ll dist[M];
int par[M];
int main(){
    int n,m;
    scanf("%i %i",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v,c,w;
        scanf("%i %i %i %i",&u,&v,&c,&w);
        E[u].pb({v,c,w});
        E[v].pb({u,c,w});
    }
    map<pair<int,int>,int> nodes;
    int tsz=n;
    for(int i=1;i<=n;i++){
        map<int,int> cnt;
        for(auto e:E[i]){
            cnt[e[1]]++;
        }
        for(auto e:E[i]){
            if(cnt[e[1]]>1){
                nodes[{i,e[0]}]=++tsz;
                AddEdge(tsz,i,0);
            }
        }
    }
    for(int i=1;i<=n;i++){
        map<int,int> cnt;
        map<int,ll> sum;
        map<int,vector<pair<int,int>>> mx;
        for(auto e:E[i]){
            cnt[e[1]]++;
            sum[e[1]]+=e[2];
            mx[e[1]].pb({e[2],e[0]});
        }
        for(auto& it:mx)sort(it.second.rbegin(),it.second.rend());
        for(auto e:E[i]){
            if(cnt[e[1]]==1){
                AddEdge(i,e[0],0);
                if(nodes.find({e[0],e[1]})!=nodes.end()){
                    AddEdge(i,nodes[{e[0],e[1]}],e[2]);
                }
            }else{
                int from=nodes[{i,e[0]}];
                int mxNode=mx[e[1]][0].second;
                int mxW=mx[e[1]][0].first;
                if(e[0]==mxNode){
                    mxNode=mx[e[1]][1].second;
                    mxW=mx[e[1]][1].first;
                }
                AddEdge(from,mxNode,sum[e[1]]-mxW-e[2]);

                int to=nodes.count({e[0],i})?nodes[{e[0],i}]:e[0];
                AddEdge(i,to,e[2]);
                AddEdge(i,e[0],sum[e[1]]-e[2]);
            }
        }
    }
    for(int i=1;i<=tsz;i++)dist[i]=inf;
    dist[1]=0;
    priority_queue<pair<ll,int>> pq;
    pq.push({0,1});
    while(pq.size()){
        int u=pq.top().second;
        ll d=-pq.top().first;
        pq.pop();
        if(d!=dist[u])continue;
        for(auto e:G[u]){
            int v;ll w;tie(v,w)=e;
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                par[v]=u;
                pq.push({-dist[v],v});
            }
        }
    }
    if(dist[n]==inf)printf("-1\n");
    else{
        printf("%lld\n",dist[n]);
        /*stack<int> stk;
        int u=n;
        while(u!=1){
            stk.push(u);
            u=par[u];
        }
        stk.push(1);
        while(stk.size()){
            printf("%i ",stk.top());
            stk.pop();
        }*/
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%i %i",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%i %i %i %i",&u,&v,&c,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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