Submission #553455

#TimeUsernameProblemLanguageResultExecution timeMemory
553455ala2Jakarta Skyscrapers (APIO15_skyscraper)C++14
0 / 100
2 ms2644 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=1e17; signed main() { ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; int ss,ee; ee=n+1; for(int i=1;i<=m;i++) { cin>>a[i]>>b[i]; if(i==1) ss=a[i]; if(i==2) ee=b[i]; } for(int i=1;i<=m;i++) { for(int j=1;j<=m;j++) { if(j==i) continue; if( dist(i,j)%b[i]==0 ){ // cout<<" "<<i<<" "<<j<<endl; v[a[i]].pb({dist(i,j)/b[i],a[j]}); } } } 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]) { dis[i.S]=ned; q.push({ned,i.S}); } } } if(dis[ee]<inf) cout<<dis[ee]<<endl; else cout<<-1<<endl; }
#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...