Submission #1165353

#TimeUsernameProblemLanguageResultExecution timeMemory
1165353pinrueiJakarta Skyscrapers (APIO15_skyscraper)C++20
57 / 100
542 ms327680 KiB
#pragma region// #include<bits/stdc++.h> //#define int long long #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma comment(linker, "/stack:200000000") #define f2(i, m) for(int i=0; i<m; i++) #define f21(i, m) for(int i=1; i<m; i++) #define f3(i, n, m) for(int i=n; i<m; i++) #define f2_(i, m) for(int i=m; i>-1; i--) #define f21_(i, m) for(int i=m; i>0; i--) #define f3_(i, n, m) for(int i=n; i>=m; i--) #define travG(idx) for(int i : g[idx]) #define travG_(i, idx) for(int i : g[idx]) #define trav(loop) for(int i : loop) #define trav_(i, loop) for(int i : loop) #define trav2(loop, idx) for(int i : loop[idx]) #define trav2_(i, loop, idx) for(int i : loop[idx]) #define ll long long #define bs bitset #define pii pair<int, int> #define vi vector<int> #define vvi vector<vector<int>> #define ve vector<element> #define ve_ vector<element_> #define vpii vector<pair<int, int>> #define qi queue<int> #define qe queue<element> #define qpii queue<pair<int, int>> #define si stack<int> #define se stack<element> #define spii stack<pair<int, int>> #define vb vector<bool> #define pqi priority_queue<int> #define pqi_ priority_queue<int, vi, greater<int>> #define pqpii priority_queue<pair<int, int>> #define pqpii_ priority_queue<pair<int, int>, vpii, greater<pii>> #define pb push_back #define pf push_front #define pob pop_back() #define pof pop_front() #define len length() #define elif else if #define mod 1000000007 #pragma endregion #define debug /* #ifdef debug #endif #ifndef debug #endif */ using namespace std; using vvpib = vector<vector<pair<int, bool>>>; using vpib = vector<pair<int, bool>>; using pib = pair<int, bool>; int n, m; signed main()// https://tioj.ck.tp.edu.tw/problems/2363 { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; /* pii input[m]; f2(i, m) cin>>input[i].first>>input[i].second; int srt=input[0].first, stp=input[1].first; sort(input, input+m, [](pii a, pii b) { return (pii){a.second, a.first%a.second} < (pii){b.second, b.first%b.second}; });*/ auto cmp = [](const pii a, const pii b) { return (pii){a.second, a.first%a.second} < (pii){b.second, b.first%b.second}; }; priority_queue<pii, vpii, decltype(cmp)> input(cmp); int tmp[n], pre=0, pre_=0; vvpib g(n); int idx = n;// maintain g.size() int a, b; cin>>a>>b; int srt=a; input.push({a, b}); cin>>a>>b; int stp=a; input.push({a, b}); f2(i, m-2) { cin>>a>>b; input.push({a, b}); } //for(pii &i : input) while(!input.empty()) { pii i = input.top(); input.pop(); if(i.second==pre && i.first%i.second==pre_) { g[i.first].pb({tmp[i.first], 0}); #ifndef debug cout<<i.first<<' '<<tmp[i.first]<<' '<<0<<'\n'; #endif } else { bool flag=0; for(int j=i.first%i.second; j<n; j+=i.second, flag=1, idx++) { g.pb({{j, 0}}); tmp[j]=idx; #ifndef debug cout<<idx<<' '<<j<<' '<<0<<'\n'; #endif if(flag) { g[idx-1].pb({idx, 1}), g[idx].pb({-1+idx, 1}); #ifndef debug cout<<idx<<' '<<idx-1<<' '<<1<<'\n'; cout<<idx-1<<' '<<idx<<' '<<1<<'\n'; #endif } } g[i.first].pb({tmp[i.first], 0}); #ifndef debug cout<<i.first<<' '<<tmp[i.first]<<' '<<0<<'\n'; #endif pre=i.second, pre_=i.first%i.second; } } // 01BFS // to fix bool vis[idx] = {0}; deque<pii> dq; dq.pb({srt, 0}); while(!dq.empty()) { pii now = dq.front(); dq.pop_front(); //cout << '\n' << now.first << ' '; for(pib &ii : g[now.first]) {int i = ii.first; //cout<<' '<<i; if(vis[i]&&i>=n) continue; vis[i]=1; if(i==stp) { cout << now.second+ii.second; return 0; } if(ii.second) dq.pb({i, now.second+1}); else dq.pf({i, now.second}); } } //cout << vis[8]; cout << -1; 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...