QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#788344 | #5073. Elden Ring | Moloch | WA | 163ms | 19184kb | C++14 | 2.7kb | 2024-11-27 16:37:14 | 2024-11-27 16:37:23 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <unordered_map>
#include <bitset>
#define int long long
#define LL long long
using namespace std;
char buf[1 << 21], *p1 = buf, *p2 = buf;
char gc()
{
if(p1 == p2){p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin);}
return *(p1) ++;
}
LL read()
{
LL x = 0, s = 1;
scanf("%lld", &x); return x;
char ch = gc();
if(ch < '0' || ch > '9'){s = ch == '-' ? -1 : s; ch = gc();}
while('0' <= ch && ch <= '9'){x = (x << 1ll) + (x << 3ll) + (ch ^ 48); ch = gc();}
return x * s;
}
const int N = 2e5 + 10;
const int INF = 1e9 + 10;;
int n, m, ai, bi;
int li[N];
vector<int> e[N];
int dis[N], st[N];
queue<int> q;
void bfs_ls()
{
int dv = ai - bi;
dis[1] = 0; st[1] = 1; q.push(1);
while(q.size())
{
int x = q.front(); q.pop();
for(int y : e[x])
{
if(st[y] || li[y] > li[1] + dv * dis[x]){continue;}
st[y] = 1; dis[y] = min(dis[x] + 1, dis[y]);
q.push(y);
}
}
}
vector<int> po[N];
int cedi(int x, int y){return x % y ? x / y + 1 : x / y;}//ceil
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII> > he;
void bfs_gr()
{
int dv = ai - bi;
// cerr << "DV:" << dv << "\n";
dis[1] = 0; st[1] = 1; po[0].push_back(1);
int prs = 0;
for(int tim = 0; tim <= n; tim ++)
{
// cerr << "TIM:" << tim << "=============================\n";
for(int x : po[tim])
{
// cerr << " P:" << x << "\n";
for(int y : e[x])
{
if(st[y]){continue;}
he.push({li[y], y}); st[y] = 1;
}
}
if(tim){prs += po[tim].size();}
while(he.size())
{
int y = he.top().second, fl = 0;
if(li[y] <= li[1] + tim * dv){dis[y] = tim + 1; po[dis[y]].push_back(y); st[y] = 1; fl = 1;}
else
{
int tmp = cedi(li[y] - li[1], dv);
if(tmp <= prs){dis[y] = tmp + 1; po[dis[y]].push_back(y); st[y] = 1; fl = 1;}
}
if(fl){he.pop();}
else{break;}
}
}
}
void init()
{
while(he.size()){he.pop();}
while(q.size()){q.pop();}
for(int i = 0; i <= n; i ++)
{
dis[i] = INF; st[i] = 0;
e[i].clear(); po[i].clear();
}
}
void solve()
{
n = read(); m = read(); ai = read(); bi = read();
init();
for(int i = 1; i <= m; i ++){int u = read(), v = read(); e[u].push_back(v); e[v].push_back(u);}
for(int i = 1; i <= n; i ++){li[i] = read();}
li[1] --;//变成小于等于
for(int i = 2; i <= n; i ++){li[i] += bi;}
if(ai <= bi){bfs_ls();}
else{bfs_gr();}
// cerr << "ANS:";
if(dis[n] <= n - 1){printf("%lld\n", dis[n]);}
else{puts("-1");}
}
signed main()
{
int tii = read();
for(int z = 1; z <= tii; z ++){solve();}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 18004kb
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: 163ms
memory: 19184kb
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 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -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 -1...
result:
wrong answer 40th numbers differ - expected: '-1', found: '7'