Submission #1275821

#TimeUsernameProblemLanguageResultExecution timeMemory
1275821_broken_Jakarta Skyscrapers (APIO15_skyscraper)C++20
36 / 100
1096 ms18560 KiB
#include <bits/stdc++.h> #define ll long long //#define int long long #define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define lc (id << 1) #define rc ((id << 1) ^ 1) using namespace std; const long long mod = 1e9 + 7, maxn = 3e4 + 9, base = 1e6 + 7; //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") int n,m,d[maxn]; vector<pair<int,int>> dog; int32_t main() { fast_io; cin >> n >> m; unordered_set<int> baghi; for(int i = 1; i <= m;i++) { int bi,pi; cin >> bi >>pi; dog.push_back({bi + 1 , pi}); baghi.insert(i-1); } priority_queue< pair<int,int> , vector < pair<int,int>> ,greater<pair<int,int>> > q; q.push({ 0 , 0}); bitset<maxn> mark; while (q.size()) { pair<int, int> aa = q.top(); q.pop(); if(mark[aa.second]) continue; d[aa.second] = aa.first; mark[aa.second] = true; baghi.erase(aa.second); int v = aa.second; if(baghi.size()) for(int i : baghi) if((dog[i].first % dog[v].second) == (dog[v].first % dog[v].second)) if(!mark[i]) q.push({d[v] + (abs(dog[i].first - dog[v].first) / dog[v].second) , i}); } if(mark[1]) cout << d[1] << "\n"; else cout << "-1\n"; }
#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...