QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#295640 | #5073. Elden Ring | zzuqy# | WA | 234ms | 22880kb | C++14 | 1.8kb | 2023-12-31 17:28:35 | 2023-12-31 17:28:35 |
Judging History
answer
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#define ll long long
#define rep(a,b,c) for(int c=a;c<=b;++c)
#define sc(A) scanf("%d",&A)
#define go(x) for(int i=lin[x];i;i=nex[i])
using namespace std;
const int MAXN = 400010;
int n, A, B, m;
int T, len, t, h;
int d[MAXN], a[MAXN], q[MAXN];
int lin[MAXN], ver[MAXN], nex[MAXN];
inline void add(int x, int y) {
ver[++len] = y;
nex[len] = lin[x];
lin[x] = len;
}
void bfs() {
h = 0;
q[t = 1] = 1;
d[1] = 1;
while (++h <= t) {
int x = q[h];
go(x) {
int tn = ver[i];
if (!d[tn] && a[1] + (ll)(d[x] - 1) * A - (ll)B * d[x] >= a[tn]) {
d[tn] = d[x] + 1;
q[++t] = tn;
}
}
}
}
namespace sub2 {
vector<int>v[MAXN];
int hi[MAXN];
void bfs() {
int cnt = 0;
for (int i = 0; i <= n + 1; i++)
v[i].clear(), d[i] = 1000000000;
for (int i = 2; i <= n; i++) {
hi[i] = max(0, (a[i] + B - a[1]) / (A - B) + 1);
if (hi[i] > MAXN)
hi[i] = MAXN - 1;
//cout << hi[i] << " ";
}
h = 0;
q[t = 1] = 1;
d[1] = 1;
while (++h <= t) {
cnt++;
int x = q[h];
go(x) {
int tn = ver[i];
if (d[tn] == 1000000000) {
if (cnt >= hi[tn]) {
d[tn] = d[x] + 1;
q[++t] = tn;
} else
v[hi[tn]].push_back(tn);
}
}
for (auto tn : v[cnt]) {
d[tn] = cnt + 1;
q[++t] = tn;
}
}
}
}
int main() {
//freopen("1.in", "r", stdin);
sc(T);
while (T--) {
sc(n);
sc(m);
sc(A);
sc(B);
len = 0;
rep(1, n, i) {
lin[i] = 0;
d[i] = 0;
}
rep(1, m, i) {
int x, y;
sc(x);
sc(y);
add(x, y);
add(y, x);
}
rep(1, n, i)sc(a[i]);
if (A <= B) {
bfs();
printf("%d\n", d[n] - 1);
} else {
sub2::bfs();
printf("%d\n", d[n]);
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 20616kb
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: -100
Wrong Answer
time: 234ms
memory: 22880kb
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:
1000000000 -1 1000000000 2 -1 -1 -1 1000000000 1000000000 -1 2 -1 -1 -1 -1 1000000000 1000000000 1000000000 1000000000 -1 -1 2 1000000000 -1 -1 1000000000 -1 -1 1000000000 1000000000 1000000000 -1 -1 1000000000 1000000000 1000000000 -1 -1 -1 1000000000 1000000000 1000000000 -1 -1 -1 -1 1000000000 10...
result:
wrong answer 1st numbers differ - expected: '-1', found: '1000000000'