# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
48488 | Kmcode | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 834 ms | 176180 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
int n;
int m;
map<pair<int, int>, vector<int> > mp;
vector<pair<int, int> > bs;
vector<int> con;
vector<int> dist;
vector<int> g[300002];
deque<int> q;
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)bs.push_back(make_pair(-1, -1));
for (int i = 0; i < n; i++)con.push_back(-1);
for (int i = 0; i < n; i++)dist.push_back(-1);
int idx = n;
int star = -1;
int en = -1;
for (int i = 0; i < m; i++) {
int b, p;
scanf("%d%d", &b, &p);
if (i == 0)star = b;
if (i == 1)en = b;
pair<int, int> base = make_pair(b%p, p);
if (!mp.count(base)) {
mp[base].clear();
auto &v = mp[base];
for (int pos = base.first; pos < n; pos += p) {
v.push_back(idx);
idx++;
bs.push_back(base);
con.push_back(pos);
dist.push_back(-1);
}
}
int ID = (b - base.first) / p;
g[b].push_back(mp[base][ID]);
}
dist[star] = 0;
q.push_back(star);
while (!q.empty()) {
int b = q.front();
q.pop_front();
if (b < n) {
for (int go : g[b]) {
if (dist[go] == -1) {
dist[go] = dist[b];
q.push_front(go);
}
}
}
else {
if (con[b] != -1) {
if (dist[con[b]] == -1) {
dist[con[b]] = dist[b];
q.push_front(con[b]);
}
}
if (bs[b] == bs[b - 1]&&dist[b-1]==-1) {
dist[b - 1] = dist[b] + 1;
q.push_back(b - 1);
}
if (b + 1 < bs.size() && bs[b] == bs[b + 1] && dist[b + 1] == -1) {
dist[b + 1] = dist[b] + 1;
q.push_back(b + 1);
}
}
}
printf("%d\n", dist[en]);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |