Submission #249695

#TimeUsernameProblemLanguageResultExecution timeMemory
249695receedJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
386 ms262148 KiB
#include <iostream> #include <iomanip> #include <cstdio> #include <vector> #include <algorithm> #include <cmath> #include <cstring> #include <cassert> #include <string> #include <set> #include <map> #include <random> #include <bitset> #include <string> #include <unordered_set> #include <unordered_map> #include <deque> #include <queue> #define rep(i, n) for (int i = 0; i < (n); i++) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; using ll = long long; using ul = unsigned long long; using ld = long double; const int N = 30001, M = 9000000; map<pair<int, int>, vector<int>> li; vector<pair<int, bool>> g[M]; int d[M], used[M]; void adde(int u, int v, bool w) { g[u].push_back({v, w}); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, cb, cp, s, t; cin >> n >> m; rep(i, m) { cin >> cb >> cp; if (i == 0) s = cb; else if (i == 1) t = cb; li[{cp, cb % cp}].push_back(cb); } int cs = n; for (auto &pp : li) { auto p = pp.first; int ck = (n - p.second + p.first - 1) / p.first; rep(i, ck - 1) { adde(cs + i, cs + i + 1, 1); adde(cs + i + 1, cs + i, 1); } rep(i, ck) adde(cs + i, p.second + i * p.first, 0); for (int i : pp.second) adde(i, cs + (i - p.second) / p.first, 0); cs += ck; } deque<int> q {s}; rep(i, cs) d[i] = M; d[s] = 0; while (!q.empty()) { int v = q.front(); q.pop_front(); if (used[v]) continue; used[v] = 1; for (auto &p : g[v]) { if (p.second) { if (d[p.first] > d[v] + 1) { d[p.first] = d[v] + 1; q.push_back(p.first); } } else if (d[p.first] > d[v]) { d[p.first] = d[v]; q.push_front(p.first); } } } if (d[t] == M) cout << -1; else cout << d[t]; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:86:12: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (d[t] == M)
         ~~~^
skyscraper.cpp:66:10: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
     d[s] = 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...