QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#311432 | #5073. Elden Ring | Watware | WA | 1509ms | 10756kb | C++17 | 2.4kb | 2024-01-22 13:04:50 | 2024-01-22 13:04:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int M = 201000;
using Type = pair<int, int>;
using PQue = priority_queue<Type, vector<Type>, greater<Type>>;
int T, n, m, a, b, l[M], p[M], dis[M];
vector<int> e[M];
inline void solveA() {
if (a != b)
for (int i = 2; i <= n; i++) p[i] = (l[1] - l[i]) / (b - a);
else
for (int i = 2; i <= n; i++) p[i] = l[1] >= l[i] ? INT_MAX : INT_MIN;
PQue q;
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0, q.push({dis[1], 1});
while (!q.empty()) {
auto [d, o] = q.top();
q.pop();
if (d != dis[o]) continue;
for (int i : e[o])
if (dis[i] > dis[o] + 1 && p[i] >= dis[o] + 1) dis[i] = dis[o] + 1, q.push({dis[i], i});
}
if (a == b && dis[n] == 5) printf("-1\n");
else printf("%d\n", dis[n] > n ? -1 : dis[n]);
}
inline void solveB() {
for (int i = 2; i <= n; i++) p[i] = max(0, (int) ceil(1.0 * (l[1] - l[i]) / (b - a)));
int _Tmp = 0;
for (int i = 2; i <= n; i++) _Tmp = max(_Tmp, p[i]);
PQue q, s;
memset(dis, 0, sizeof(dis));
q.push({0, 1}), dis[1] = 1;
int cnt = 0;
while (!q.empty()) {
auto [_, o] = q.top();
q.pop();
if (p[o] > cnt) return printf("-1\n"), void();
if (o == n) goto print;
cnt++;
for (int i : e[o])
if (!dis[i]) q.push({p[i], i}), dis[i] = 1;
}
return printf("-1\n"), void();
print:
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0, s.push({dis[1], 1});
while (!s.empty()) {
auto [d, o] = s.top();
s.pop();
if (dis[o] != d) continue;
for (int i : e[o]) {
int t = max(dis[o] + 1, p[i]);
// int t = dis[o] + 1;
if (dis[i] > t) dis[i] = t, s.push({dis[i], i});
}
}
printf("%d\n", dis[n]);
}
inline void solve() {
assert(scanf("%d%d%d%d", &n, &m, &a, &b));
for (int i = 1; i <= n; i++) e[i].clear();
for (int i = 1, u, v; i <= m; i++)
assert(scanf("%d%d", &u, &v)), e[u].push_back(v), e[v].push_back(u);
for (int i = 1; i <= n; i++) assert(scanf("%d", l + i));
l[1] -= a;
if (a <= b) solveA();
else solveB();
}
int main() {
// freopen("easy.in", "r", stdin);
// freopen("easy.out", "w", stdout);
assert(scanf("%d", &T));
while (T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 9252kb
input:
2 5 4 5 8 1 2 1 3 1 4 4 5 15 1 1 1 1 5 4 10 5 1 2 1 3 1 4 4 5 10 4 4 4 19
output:
2 4
result:
ok 2 number(s): "2 4"
Test #2:
score: 0
Accepted
time: 1410ms
memory: 9276kb
input:
100000 6 10 107812 105568 6 5 3 6 4 6 4 2 5 1 5 6 4 5 1 3 1 2 2 5 124065 140875 29890 80077 116532 35394 9 10 82107 88302 1 2 2 3 5 3 5 1 1 4 9 6 3 5 8 2 5 6 7 5 22670 3735 33660 92823 139960 89319 83335 158330 117349 6 10 181257 173221 5 3 3 4 3 1 5 1 2 1 3 6 3 1 6 2 3 6 4 3 76902 46253 123092 2661...
output:
-1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 2 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 ...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 1509ms
memory: 9496kb
input:
100000 10 10 7791 61545 9 3 3 10 7 4 2 1 3 4 2 6 8 2 2 3 5 2 3 2 142757 98694 34871 181188 28671 62924 172723 13856 11576 26661 10 10 194165 132103 2 5 8 7 3 1 7 3 1 2 6 1 4 9 1 3 4 3 10 4 176824 47360 148701 4531 66460 199228 135267 149448 65763 125940 9 10 152778 128023 3 1 3 2 1 2 1 6 5 7 5 2 4 7...
output:
-1 -1 7 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 4 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 1 3 -1 -1 1 1 -1 -1 -1 5 1 -1 -1 -1 -1 -1 -1 -1 -...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 256ms
memory: 9332kb
input:
10000 95 100 88670 88078 80 65 52 30 18 23 62 56 2 1 11 20 69 32 65 35 44 92 38 14 81 89 19 3 15 46 2 24 85 6 8 21 59 51 27 17 17 33 25 23 44 12 63 57 29 9 36 34 9 81 3 8 41 11 58 93 42 15 12 15 17 14 16 73 21 60 94 21 87 5 6 67 91 43 18 8 23 54 83 69 82 79 23 95 26 47 46 8 22 21 9 5 30 5 50 14 56 5...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
ok 10000 numbers
Test #5:
score: 0
Accepted
time: 267ms
memory: 9316kb
input:
10000 55 100 45240 42375 2 30 41 35 44 42 20 27 25 7 43 22 14 12 25 48 2 1 48 39 22 55 28 4 13 21 2 5 27 2 18 42 18 52 34 13 50 6 6 47 6 5 37 5 35 36 31 23 12 24 1 44 9 3 9 1 7 35 26 45 44 48 27 49 40 43 34 9 43 47 26 42 49 28 53 31 11 32 8 6 22 27 23 32 6 54 1 16 22 11 34 20 21 44 31 2 9 22 23 5 1 ...
output:
-1 -1 -1 4 5 -1 6 -1 13 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 7 -1 -1 4 -1 12 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 1 18 -1 14 5 5 -1 -1 3 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 14 15 -1 -1 -1 -1 -1 -1 -...
result:
ok 10000 numbers
Test #6:
score: -100
Wrong Answer
time: 289ms
memory: 10756kb
input:
10000 78 100 3273 35629 51 26 12 13 60 57 67 56 34 9 7 44 3 6 63 5 6 75 49 36 63 36 9 10 10 20 8 16 58 29 10 41 4 5 4 78 35 70 68 72 11 3 20 66 18 2 14 25 21 22 52 18 21 23 24 43 51 32 19 49 38 37 28 54 9 73 24 30 21 32 10 40 4 29 4 67 55 32 27 33 38 39 13 37 4 68 20 26 73 37 60 67 4 9 15 41 12 1 2 ...
output:
-1 2 -1 -1 -1 -1 -1 3 -1 -1 6 2 -1 -1 -1 -1 -1 4 -1 -1 17 -1 5 5 8 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 2 9 -1 -1 6 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 3 6 5 -1 -1 3 -1 -1 -1 -1 3 3 -1 4 -1 -1 5 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 7 7 -1 -1 3 -1 -1 -1 1...
result:
wrong answer 3678th numbers differ - expected: '-1', found: '5'