Submission #1221982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221982		TadijaSebez	Robot (JOI21_ho_t4)	C++20	24 / 100	3085 ms	1060600 KiB

Main

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

const int N=100050;
const int M=3*N;
vector<array<int,3>> E[N];
vector<pair<int,int>> G[M];
void AddEdge(int u,int v,int w){
    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 col:cnt){
            if(col.second==2){
                nodes[{i,col.first}]=++tsz;
                AddEdge(tsz,i,0);
            }
        }
    }
    for(int i=1;i<=n;i++){
        map<int,int> cnt;
        map<int,ll> sum;
        for(auto e:E[i]){
            cnt[e[1]]++;
            sum[e[1]]+=e[2];
        }
        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 if(cnt[e[1]]==2){
                int n2=nodes[{i,e[1]}];
                AddEdge(n2,e[0],0);
                if(nodes.find({e[0],e[1]})!=nodes.end()){
                    AddEdge(n2,nodes[{e[0],e[1]}],e[2]);
                }

                AddEdge(i,e[0],sum[e[1]]-e[2]);
                if(nodes.find({e[0],e[1]})!=nodes.end()){
                    AddEdge(i,nodes[{e[0],e[1]}],e[2]);
                }else{
                    AddEdge(i,e[0],e[2]);
                }
            }else{
                AddEdge(i,e[0],sum[e[1]]-e[2]);
                if(nodes.find({e[0],e[1]})!=nodes.end()){
                    AddEdge(i,nodes[{e[0],e[1]}],e[2]);
                }else{
                    AddEdge(i,e[0],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,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("%i\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:95:18: warning: format '%i' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   95 |         printf("%i\n",dist[n]);
      |                 ~^    ~~~~~~~
      |                  |          |
      |                  int        long long int
      |                 %lli
Main.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%i %i",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%i %i %i %i",&u,&v,&c,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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