Submission #1230266

#TimeUsernameProblemLanguageResultExecution timeMemory
1230266marselelJakarta Skyscrapers (APIO15_skyscraper)C++20
0 / 100
1 ms1096 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; # define all(a) a.begin(), a.end() # define rall(a) a.rbegin(), a.rend() # define pii pair<int, int> # define pll pair<ll, ll> #ifdef LOCAL #include "algo/debug.h" #else # define debug(x) #endif constexpr int inf = 0x3f3f3f3f; constexpr ll INF = 2e15; const ld RANDMAX = (1LL << 32) - 1; const ll mod = 1'000'000'007; ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// const int maxn = 30'010; vector<pii> g[maxn]; void solve() { int n, m; cin >> n >> m; vector<pii> a[n]; for (int i = 0; i < m; ++i) { int b, p; cin >> b >> p; a[b].push_back({i, p}); } for (int i = 0; i < n; ++i) { for (auto [ind, p] : a[i]) { for (int j = i + p; j < n; j += p) { for (auto [ind2, _] : a[j]) { g[ind].push_back({ind2, (j - i) / p}); debug(ind); debug(ind2); } } for (int j = i - p; j >= 0; j -= p) { for (auto [ind2, _] : a[j]) { g[ind].push_back({ind2, (i - j) / p}); debug(ind); debug(ind2); } } } } vector<int> dist(m, inf); vector<bool> used(m); dist[0] = 0; for (int i = 0; i < m; ++i) { int v = -1; debug(dist); for (int j = 0; j < m; ++j) { if (!used[j] && (v == -1 || dist[j] < dist[v])) { v = j; } } debug(v); if (dist[v] == inf) { cout << -1; return; } if (v == 1) { cout << dist[v]; return; } used[v] = 1; for (auto [to, w] : g[v]) { if (dist[to] > dist[v] + w) { dist[to] = dist[v] + w; } } } cout << -1; } signed main() { #ifdef LOCAL (void)!freopen("input.txt", "r", stdin); #else std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); #endif int tt = 1; //cin >> tt; /* Бисмил ляяхи ррахмаани ррахиим. Изаа джаа’э насрул лаахи валь фатх. Ва ра’этэ нааса ядхулююнэ фии дии нил ляяхи афвааджа. Фа саббих би хамди раббикя вастагфирхь. Иннаху кяяна тавваабэ Бисмил ляяхи ррахмаани ррахиим. Куль а‘уузу би раббин наас. Мааликин наас. Иляяхин наас. Мин шарриль васваасиль ханнаас. Аллязии ювасвису фии судуурин наас. Миналь джиннати ван наас Бисмил ляяхи ррахмаани ррахиим. Куль яяайюхэль кяяфируун. Ляя а‘буду маа та‘будуун. Ва ляя энтум ‘аабиду унэ маа а‘буд. Ва ляя ана ‘аабидум маа ‘абадтум. Ва ляя энтум ‘аабидуунэ маа а‘буд. Лякум диинукум ва лияд диин */ while (tt--) { solve(); cout << '\n'; } cerr << "\nRuntime = " << ((ld)clock() / CLOCKS_PER_SEC) << " ms\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...