QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#604352 | #5073. Elden Ring | AngelOlan | WA | 200ms | 3764kb | C++20 | 2.3kb | 2024-10-02 10:14:35 | 2024-10-02 10:14:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
// Pura Gente del Coach Moy
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
#define pb push_back
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define FOR(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define ROF(i, a, b) for (int i = (int)a - 1; i >= (int)b; --i)
#define ENDL '\n'
constexpr int INF = 1e9 + 5;
void solve_less_eq(int A, int B, vector<vi>& g, vi& a) {
int N = SZ(g);
vi d(N, -1);
d[0] = 0;
queue<int> q;
q.push(0);
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto &v : g[u]) if (d[v] == -1 && (ll)A * d[u] + a[0] > (ll)B * d[u] + a[v]) {
d[v] = d[u] + 1;
q.push(v);
}
}
cout << d[N - 1] << ENDL;
}
int find_max_time(int D, vector<vi>& g, vi& a) {
int N = SZ(g), t = -1;
vi vis(N);
vis[0] = 1;
priority_queue<pi> pq;
pq.push({1, 0});
while (!pq.empty() && -pq.top().first <= t) {
int u = pq.top().second;
pq.pop();
for (auto &v : g[u]) if (!vis[v]) {
vis[v] = 1;
int dv = a[v] <= a[0] ? 0 : ((a[v] - a[0]) / D + 1);
pq.push({-dv, v});
}
++t;
}
return t;
}
void solve_greater(int D, vector<vi>& g, vi& a) {
int N = SZ(g);
vi d(N, INF);
d[0] = 0;
priority_queue<pi> pq;
pq.push({0, 0});
int mx_time = find_max_time(D, g, a);
while (!pq.empty()) {
auto [du, u] = pq.top();
du = -du;
pq.pop();
if (du > d[u]) continue;
for (auto &v : g[u]) {
int y = a[v] <= a[0] ? 0 : ((a[v] - a[0]) / D + 1);
int dx = max(du, y);
if (dx <= mx_time && dx + 1 < d[v]) {
d[v] = dx + 1;
pq.push({-d[v], v});
}
}
}
if (d[N - 1] == INF) d[N - 1] = -1;
cout << d[N - 1] << ENDL;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
int N, M, A, B;
cin >> N >> M >> A >> B;
vector<vi> g(N);
while (M--) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].pb(v), g[v].pb(u);
}
vi a(N);
FOR (i, 0, N) {
cin >> a[i];
if (i) a[i] += B;
}
if (A <= B) solve_less_eq(A, B, g, a);
else solve_greater(A - B, g, a);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
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: 184ms
memory: 3504kb
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: 192ms
memory: 3628kb
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: 188ms
memory: 3656kb
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: 195ms
memory: 3764kb
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: 200ms
memory: 3624kb
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'