QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #545414 | #5073. Elden Ring | taiyuu | WA | 48ms | 9012kb | C++14 | 1.6kb | 2024-09-03 11:55:02 | 2024-09-03 11:55:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int re(){
int num=0,fl=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-') fl=-1;ch=getchar();}
while(isdigit(ch)){num=num*10+ch-'0';ch=getchar();}
return num*fl;
}
const int N=2e5+100;
const int M=4e5+100;
int n,m,T,tu,tv,head[N],nxt[M],ver[M],dis[N],c[N],tot=1,a,b;
void adde(int tu,int tv){
nxt[++tot]=head[tu];
head[tu]=tot;
ver[tot]=tv;
}
void sol1(){
queue<int> q;
q.push(1);dis[1]=0;
while(!q.empty()){
int x=q.front();q.pop();
if(x==n){
cout<<dis[n]<<"\n";return;
}
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(dis[y]) continue;
if(c[1]+a*dis[x]>=c[y]+(dis[x]+1)*b){
dis[y]=dis[x]+1;
q.push(y);
}
else
dis[y]=-1;
}
}
cout<<-1<<"\n";
return ;
}
void sol2(){
priority_queue<pair<int,int> > q;
q.push(make_pair(0,1));dis[1]=0;
while(!q.empty()){
int x=q.top().second;q.pop();
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(dis[y]) continue;
dis[y]=max(dis[x]+1,max(0,(c[y]-c[1]+a)/(a-b)+((c[y]-c[1]+a)%(a-b)==0?0:1)));
q.push(make_pair(-dis[y],y));
}
}
sort(dis+1,dis+n);
for(int i=1;i<dis[n];++i){
if(i<dis[i+1]){
cout<<"-1\n";return;
}
}
cout<<dis[n]<<"\n";
return ;
}
int main(){
T=re();
while(T--){
for(int i=1;i<=n;++i)
head[i]=dis[i]=0;
for(int i=1;i<=m;++i)
nxt[i]=ver[i]=0;
n=re();m=re();a=re();b=re();
for(int i=1;i<=m;++i){
tu=re();tv=re();
adde(tu,tv);adde(tv,tu);
}
for(int i=1;i<=n;++i)
c[i]=re();
if(a<=b) sol1();
else sol2();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5608kb
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: 48ms
memory: 9012kb
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 -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 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 -...
result:
wrong answer 22nd numbers differ - expected: '2', found: '-1'