Submission #494322

#TimeUsernameProblemLanguageResultExecution timeMemory
494322keertanCrocodile's Underground City (IOI11_crocodile)C++17
100 / 100
565 ms49392 KiB
#include "crocodile.h" #include<bits/stdc++.h> using namespace std; #define all(x) x.begin(),x.end() #define all1(x) x.rbegin(),x.rend() #define sz(x) (int)(x.size()) const int N=1e4+5,N1=1e18,mod=1e9+7; int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){ int n,m,k; n=N; m=M; k=K; using gh=pair<int,int>; vector<pair<int,int>> adj[n]; for (int i=0,u,v,w;i<m;i++){ u=R[i][0],v=R[i][1],w=L[i]; adj[u].emplace_back(v,w); adj[v].emplace_back(u,w); } vector<gh> dis(n,{N1,N1}); priority_queue<gh,vector<gh>,greater<gh>> q; vector<bool> vis(n); for (int i=0,x;i<k;i++){ x=P[i]; q.emplace(0,x); dis[x]={0,0}; } while(!q.empty()){ int u,dis1; tie(dis1,u)=q.top(); q.pop(); //cerr<<u<<" "<<dis1<<"\n"; if (vis[u]){continue;} vis[u]=1; for (const gh &it:adj[u]){ int cur=dis1+it.second; if (dis[it.first].first>=cur){ dis[it.first].second=dis[it.first].first; dis[it.first].first=cur; } else if (cur<dis[it.first].second){ dis[it.first].second=cur; } if (dis[it.first].first!=N1 && dis[it.first].second!=N1 && !vis[it.first]){ q.emplace(dis[it.first].second,it.first); } } } return dis[0].second; }

Compilation message (stderr)

crocodile.cpp:8:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    8 | const int N=1e4+5,N1=1e18,mod=1e9+7;
      |                      ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...