# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
249240 | rdd6584 | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 1096 ms | 99832 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;
typedef pair<int ,int> pii;
char visit[30000];
unordered_map<int,int> dist[30000];
int dp[30000][100]; // 거리 100 이하일 때,
vector<int> v[30000];
int main() {
int n, m;
scanf("%d %d", &n, &m);
int st, ed;
for (int i = 0; i < m; i++) {
int a,b;
scanf("%d %d" ,&a, &b);
v[a].push_back(b);
if (i==0) st = a;
else if (i==1) ed = a;
}
memset(dp, -1, sizeof(dp));
queue<pii> q;
for (int i : v[st]) {
if (i < 100) dp[st][i] = 0;
else dist[st][i] = 0;
q.push({st, i});
}
while (!q.empty()) {
pii tv = q.front();
q.pop();
int me;
if (tv.second < 100) me = dp[tv.first][tv.second];
else me = dist[tv.first][tv.second];
if (tv.first == ed) return !printf("%d", me);
int ne;
if (tv.second < 100) {
for (int dir = -1; dir <= 1; dir += 2) {
ne = tv.first + dir * tv.second;
if (ne < 0 || ne >= n) continue;
if (dp[ne][tv.second] == -1) {
int flag = 0;
if (!visit[ne]) {
visit[ne] = 1;
for (int i : v[ne]) {
if (i < 100) dp[ne][i] = me + 1;
else dist[ne][i] = me + 1;
q.push({ne, i});
flag |= i == tv.second;
}
}
if (!flag) {
q.push({ne, tv.second});
dp[ne][tv.second] = me + 1;
}
}
}
}
else {
for (int dir = -1; dir <= 1; dir += 2) {
ne = tv.first + dir * tv.second;
if (ne < 0 || ne >= n) continue;
if (dist[ne].find(tv.second) == dist[ne].end()) {
int flag = 0;
if (!visit[ne]) {
visit[ne] = 1;
for (int i : v[ne]) {
if (i < 100) dp[ne][i] = me + 1;
else dist[ne][i] = me + 1;
q.push({ne, i});
flag |= i == tv.second;
}
}
if (!flag) {
q.push({ne, tv.second});
dist[ne][tv.second] = me + 1;
}
}
}
}
}
printf("-1");
}
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... |