Submission #553463

#TimeUsernameProblemLanguageResultExecution timeMemory
553463ala2Jakarta Skyscrapers (APIO15_skyscraper)C++14
36 / 100
249 ms262144 KiB
#include <bits/stdc++.h> #define int long long #define F first #define S second #define pb push_back #define B begin() #define E end() using namespace std; int a[300010]; int b[300010]; vector<pair<int,int>>v[100100]; int dist(int i,int j) { return abs(a[j]-a[i]); } int dis[100100]; const int inf=1e18; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; int ss,ee; for(int i=1;i<=m;i++) { cin>>a[i]>>b[i]; if(i==1) ss=a[i]; if(i==2) ee=a[i]; } for(int i=1;i<=m;i++) { int g=0; for(int j=a[i]-b[i];j>=0;j-=b[i]) { g++; //cout<<" "<<a[i]<<" "<<j<<" "<<g<<endl; v[a[i]].pb({g,j}); } g=1; for(int j=a[i]+b[i];j<n;j+=b[i]) { // cout<<" "<<a[i]<<" "<<j<<" "<<g<<endl; v[a[i]].pb({g,j}); g++; } } if(ss==ee) { cout<<0<<endl; return 0; } // for(int i=0;i<=n;i++) // sort(v[i].B,v[i].E); for(int i=0;i<=n+1;i++) { dis[i]=inf; } dis[ss]=0; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q; q.push({0,ss}); while(!q.empty()) { // cout<<"D"; pair<int,int>x=q.top(); q.pop(); // cout<<" :::: "<<x.S<<endl; for(auto i:v[x.S]) { int ned=x.F+i.F; // cout<<" "<<i.F<<" "<<ned<<endl; if(ned<dis[i.S]) { //cout<<" "<<i.S<<" "<<ned<<" "<< dis[i.S]=ned; q.push({ned,i.S}); } } } if(dis[ee]<inf) cout<<dis[ee]<<endl; else cout<<-1<<endl; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:89:22: warning: 'ee' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |             if(dis[ee]<inf)
      |                ~~~~~~^
skyscraper.cpp:66:20: warning: 'ss' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |             dis[ss]=0;
      |             ~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...