Submission #1167124

#TimeUsernameProblemLanguageResultExecution timeMemory
1167124AMnuJakarta Skyscrapers (APIO15_skyscraper)C++17
10 / 100
1 ms1096 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second typedef pair<int,int> pii; const int MAXN = 3e4+5; bitset <105> bs[MAXN]; int b[MAXN], p[MAXN]; vector <int> adj[MAXN]; vector <int> pq[2]; int main(){ ll n, m; cin >> n >> m; for(int i = 1; i <= m; i++) cin >> b[i] >> p[i]; for(int i = 1; i <= m; i++){ adj[b[i]].push_back(p[i]); } pq[0].push_back(b[1]); for(int dist=0;!pq[dist&1].empty();dist++){ for (auto idx : pq[dist&1]) { if (idx == b[2]) { cout << dist << "\n"; return 0; } for(auto i : adj[idx]){ // cout << idx << " " << i << "\n"; bs[idx].set(i); if(idx+i < n && !bs[idx+i][i]){ bs[idx+i].set(i); pq[dist&1^1].push_back(idx+i); adj[idx+i].push_back(i); } if(idx-i >= 0 && !bs[idx-i][i]){ bs[idx-i].set(i); pq[dist&1^1].push_back(idx-i); adj[idx-i].push_back(i); } } adj[idx].clear(); } pq[dist&1].clear(); } 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...