Submission #380378

#TimeUsernameProblemLanguageResultExecution timeMemory
380378dannyboy20031204Jakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
1 ms492 KiB
#include<bits/stdc++.h> #define ll long long #define fi first #define se second using namespace std; const int N = 2e5 + 5, inf = 1e9 + 7; // struct node{ int a, b, dis; }; int main(){ ios::sync_with_stdio(0), cin.tie(0); int n, m; cin >> n >> m; queue<node> q; vector<int> pos[n]; int d[m], x[m]; for (int i = 0; i < m; i++){ int x[i]; cin >> x[i] >> d[i]; pos[x[i]].push_back(i); } bitset<1000> vis[m]{}; int ans = inf; q.push({0, x[0], 0}); vis[0][x[0]] = true; while(!q.empty()){ node u = q.front(); q.pop(); //cout << u.a << ' ' << u.b << ' ' << u.dis << '\n'; if (u.b + d[u.a] < n and !vis[u.a][u.b + d[u.a]]){ q.push({u.a, u.b + d[u.a], u.dis + 1}); vis[u.a][u.b + d[u.a]] = true; } if (u.b - d[u.a] >= 0 and !vis[u.a][u.b - d[u.a]]){ q.push({u.a, u.b - d[u.a], u.dis + 1}); vis[u.a][u.b - d[u.a]] = true; } while (!pos[u.b].empty()){ int v = pos[u.b].back(); pos[u.b].pop_back(); if (!vis[v][u.b]){ q.push({v, u.b, u.dis}); vis[v][u.b] = true; } } if (u.a == 1) ans = min(ans, u.dis); } cout << ans; }
#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...