Submission #1196923

#TimeUsernameProblemLanguageResultExecution timeMemory
1196923jokerJakarta Skyscrapers (APIO15_skyscraper)C++20
36 / 100
1097 ms32584 KiB
#include<bits/stdc++.h> #include<vector> using namespace std; #define ll long long #define mk(a,b) make_pair(a,b) void solve() { int n,m; cin >> n >> m; vector<pair<int,int>> a(m); map<int,vector<int>> mp; for (int i = 0; i < m; i++) { cin >> a[i].first >> a[i].second; mp[a[i].first%a[i].second].push_back(i); } vector<vector<pair<int,int>>> GRAPH(m,vector<pair<int,int>>()); for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { if (abs(a[j].first-a[i].first)%a[i].second == 0) { GRAPH[i].push_back(mk(j,abs(a[j].first-a[i].first)/a[i].second)); } } } vector<ll> distance(m,1e18); distance[0]=0; set<pair<ll,ll>> s; for(int i=0;i<m;i++)s.insert(mk(distance[i],i)); while(s.size()){ pair<ll,ll> t=*s.begin(); s.erase(s.begin()); ll ind=t.second; for(auto i:GRAPH[ind]){ ll nd=distance[ind]+i.second; if(nd<distance[i.first]){ s.erase(mk(distance[i.first],i.first)); distance[i.first]=nd; s.insert(mk(distance[i.first],i.first)); } } } if (distance[1] == 1e18) cout << "-1\n"; else cout << distance[1] << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) { solve(); } return 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...