제출 #671606

#제출 시각아이디문제언어결과실행 시간메모리
671606MohammadAghilJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1092 ms45560 KiB
#include <bits/stdc++.h> // #pragma GCC optimize ("Ofast,unroll-loops") // #pragma GCC target ("avx2") using namespace std; typedef long long ll; typedef pair<int, int> pp; #define per(i,r,l) for(int i = (r); i >= (l); i--) #define rep(i,l,r) for(int i = (l); i < (r); i++) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define pb push_back #define ss second #define ff first void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);} void IOS(){ cin.tie(0) -> sync_with_stdio(0); #ifndef ONLINE_JUDGE #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl #else #define er(args ...) 0 #endif } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 1e9 + 7, maxn = 3e4 + 5, lg = 22, inf = ll(1e9) + 5; ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;} vector<int> dog[maxn]; map<pp, int> dist; bool vis[maxn]; int main(){ IOS(); int n, m; cin >> n >> m; map<pp, vector<int>> is; pp bg, en; rep(i,0,m){ int x, p; cin >> x >> p; if(!i) bg = {x, p}; if(i == 1) en = {x, p}; dog[x].pb(p); } deque<pp> q; q.pb({bg}); dist[bg] = 0; while(sz(q)){ auto[x, p] = q.front(); q.pop_front(); auto add = [&](int x2, int p2, bool bk){ if(x2 > -1 && x2 < n && !dist.count({x2, p2})){ dist[{x2, p2}] = dist[{x, p}] + bk; if(bk) q.pb({x2, p2}); else q.push_front({x2, p2}); } }; if(!vis[x]){ for(int r: dog[x]){ add(x, r, false); } } vis[x] = true; add(x+p, p, true), add(x-p, p, true); } cout << (dist.count(en)? dist[en]: -1) << '\n'; return 0-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...