Submission #555976

#TimeUsernameProblemLanguageResultExecution timeMemory
555976MurotYJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
1096 ms135276 KiB
// author : Murot_06 #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ff first #define ll long long #define ss second using namespace std; const int N=1e6+7, M=1e9+7; ll a[N]; vector <pair <ll,ll>> g[N]; set <ll> v[N]; void solve() { int n, m; cin >> n >> m; for (int i=1;i<=m;i++){ ll x, y; cin >> x >> y; a[i]=x; v[x].insert(y); } for (int i=0;i<n;i++){ for (auto l:v[i]){ for (int j=i+l;j<n;j+=l){ g[i].push_back({j, (j-i)/l}); // if (v[j].count(l)) break; } for (int j=i-l;j>=0;j-=l){ g[i].push_back({j, (i-j)/l}); // if (v[j].count(l)) break; } } } // priority_queue<int, vector<int>, greater<int> > priority_queue <ll, vector <ll> , greater <ll>> q; vector <ll> d(n+10, 1e18); d[a[1]]=0; q.push(a[1]); while (!q.empty()){ ll x=q.top(); q.pop(); for (auto l:g[x]){ if (d[l.ff] > d[x]+l.ss){ d[l.ff]=d[x]+l.ss; q.push(l.ff); } } } ll ans=d[a[2]]; if (ans == 1e18) ans=-1; cout << ans; return ; } int main() { ios; 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...