QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#283958 | #5073. Elden Ring | C1942huangjiaxu | WA | 160ms | 10364kb | C++14 | 1.3kb | 2023-12-15 19:28:45 | 2023-12-15 19:28:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int T,n,m,A,B,l[N],c[N],d[N];
vector<int>e[N];
void solve1(){
for(int i=2;i<=n;++i)if(l[i]>=l[1])c[i]=0;else c[i]=(A==B)?n:(l[1]-l[i]-1)/(B-A)+1;
queue<int>q;
q.push(1);
while(!q.empty()){
int u=q.front();
q.pop();
for(auto v:e[u])if(d[v]==-1&&d[u]+1<=c[v]){
d[v]=d[u]+1;
q.push(v);
}
}
}
void solve2(){
for(int i=2;i<=n;++i)c[i]=l[i]<l[1]?0:(l[i]-l[1])/(A-B)+1;
priority_queue<pair<int,int> >q;
for(auto v:e[1])if(d[v]==-1)q.push(make_pair(-c[v],v));
for(int i=1,tt=0;!q.empty()&&i<=n;++i){
vector<int>tmp;
while(!q.empty()){
int u=q.top().second;
if(d[u]!=-1){
q.pop();
continue;
}
if(c[u]<=min(i-1,tt)){
d[u]=i,q.pop();
tmp.push_back(u);
}else break;
}
tt+=tmp.size();
for(auto u:tmp)
for(auto v:e[u])if(d[v]==-1)q.push(make_pair(-d[v],v));
}
}
void solve(){
scanf("%d%d%d%d",&n,&m,&A,&B);
for(int i=1;i<=n;++i)e[i].clear(),d[i]=-(i>1);
for(int i=1,x,y;i<=m;++i){
scanf("%d%d",&x,&y);
e[x].push_back(y),e[y].push_back(x);
}
for(int i=1;i<=n;++i){
scanf("%d",&l[i]);
if(i>1)l[i]+=B;
}
if(A<=B)solve1();
else solve2();
printf("%d\n",d[n]);
}
int main(){
scanf("%d",&T);
while(T--)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 9848kb
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: 160ms
memory: 10364kb
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 -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 2 -1 -1 -1 -1 -1...
result:
wrong answer 59th numbers differ - expected: '3', found: '-1'