Submission #380646

#TimeUsernameProblemLanguageResultExecution timeMemory
380646dannyboy20031204Jakarta Skyscrapers (APIO15_skyscraper)C++17
100 / 100
286 ms48492 KiB
#include<bits/stdc++.h> #define ll long long #define fi first #define se second using namespace std; const int N = 200, inf = 1e9 + 7; // #define node pair<pair<int, int>, int> #define mode first.first #define a first.second #define b second int n, m; int f(node i){ if (i.mode == 0) return n * i.a + i.b; else return N * i.a + i.b / N; } int main(){ ios::sync_with_stdio(0), cin.tie(0); cin >> n >> m; int x[m], d[m]; bitset<201 * 30000> vis[2]{}; int dis[2][201 * 30000]; vector<int> on[n]; for (int i = 0; i < m; i++){ cin >> x[i] >> d[i]; on[x[i]].push_back(i); } deque<node> q; if (d[0] < N) q.push_back({{0, d[0]}, x[0]}); else q.push_back({{1, 0}, x[0]}); vis[d[0] < N ? 0 : 1][f(q.front())] = true; while (!q.empty()){ node u = q.front(); q.pop_front(); //cout << dis[u] << ' ' << u.a << ' ' << u.b << ' ' << '\n'; if (u.mode == 0){ if (u.b + u.a < n and !vis[0][f({{0, u.a}, u.b + u.a})]){ q.push_back({{0, u.a}, u.b + u.a}); dis[0][f({{0, u.a}, u.b + u.a})] = dis[0][f(u)] + 1; vis[0][f({{0, u.a}, u.b + u.a})] = true; } if (u.b - u.a >= 0 and !vis[0][f({{0, u.a}, u.b - u.a})]){ q.push_back({{0, u.a}, u.b - u.a}); dis[0][f({{0, u.a}, u.b - u.a})] = dis[0][f(u)] + 1; vis[0][f({{0, u.a}, u.b - u.a})] = true; } } else { if (u.b + d[u.a] < n and !vis[1][f({{1, u.a}, u.b + d[u.a]})]){ q.push_back({{1, u.a}, u.b + d[u.a]}); dis[1][f({{1, u.a}, u.b + d[u.a]})] = dis[1][f(u)] + 1; vis[1][f({{1, u.a}, u.b + d[u.a]})] = true; } if (u.b - d[u.a] >= 0 and !vis[1][f({{1, u.a}, u.b - d[u.a]})]){ q.push_back({{1, u.a}, u.b - d[u.a]}); dis[1][f({{1, u.a}, u.b - d[u.a]})] = dis[1][f(u)] + 1; vis[1][f({{1, u.a}, u.b - d[u.a]})] = true; } } while (!on[u.b].empty()){ int v = on[u.b].back(); on[u.b].pop_back(); if (d[v] < N and !vis[0][f({{0, d[v]}, u.b})]){ dis[0][f({{0, d[v]}, u.b})] = dis[u.mode][f(u)]; vis[0][f({{0, d[v]}, u.b})] = true; q.push_front({{0, d[v]}, u.b}); } else if (d[v] >= N and !vis[1][f({{1, v}, u.b})]){ dis[1][f({{1, v}, u.b})] = dis[u.mode][f(u)]; vis[1][f({{1, v}, u.b})] = true; q.push_front({{1, v}, u.b}); } } if (u.b == x[1]){ cout << dis[u.mode][f(u)]; return 0; } } cout << -1; }
#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...