QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #396597 | #5073. Elden Ring | 321625 | WA | 156ms | 10744kb | C++14 | 2.1kb | 2024-04-22 21:54:48 | 2024-04-22 21:54:48 |
Judging History
answer
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
const int N=2e5+7;
typedef long long ll;
std::vector<int> to[N];
struct pii{int v,d;};
bool operator<(pii x,pii y){return x.d>y.d;}
std::priority_queue<pii> pq;
int h[N],c[N],dis[N];bool vis[N];
inline int cldiv(int a,int b){return (a+b-1)/b;}
inline int fldiv(int a,int b){if(!b)return a>=0?1e9:-1;return a>=0?a/b:(a-b+1)/b;}
int main()
{
int T,n,m,A,B,eu,ev;scanf("%d",&T);
int firn;
for(int cas=1;cas<=T;++cas)
{
scanf("%d%d%d%d",&n,&m,&A,&B);if(cas==1)firn=n;
for(int i=1;i<=n;++i)to[i].clear();
while(m--)scanf("%d%d",&eu,&ev),to[eu].push_back(ev),to[ev].push_back(eu);
for(int i=1;i<=n;++i)scanf("%d",h+i),i>1&&(h[i]+=B,0);
if(A<=B)
{
const int D=B-A;
for(int i=2;i<=n;++i)c[i]=fldiv(h[1]-h[i]-1,D);//,printf("c[%d]=%d\n",i,c[i]);
memset(dis+1,0x3f,n*sizeof*dis);memset(vis+1,0,n*sizeof*vis);
pq.push({1,dis[1]=0});
while(!pq.empty())
{
int i=pq.top().v;pq.pop();if(vis[i])continue;
for(int v:to[i])if(dis[i]+1<std::min(dis[v],c[v]+2))pq.push({v,dis[v]=dis[i]+1});
}
}
else
{
const int D=A-B;int H=c[1]=-1;memset(vis+1,0,n*sizeof*vis);
for(int i=2;i<=n;++i)c[i]=(h[i]<=h[1]?0:cldiv(h[i]-h[1]+1,D));
// ,printf("c[%d]=%d\n",i,c[i]);
pq.push({1,0});vis[1]=1;
while(!pq.empty())
{
int i=pq.top().v;pq.pop();/*printf("i=%d H=%d\n",i,H);*/if(H<c[i])break;++H;
for(int v:to[i])if(!vis[v])pq.push({v,c[v]}),vis[v]=1;
}
while(!pq.empty())pq.pop();
// printf("H=%d\n",H);
memset(dis+1,0x3f,n*sizeof*dis);memset(vis+1,0,n*sizeof*vis);
int t;pq.push({1,dis[1]=0});
while(!pq.empty())
{
int i=pq.top().v;pq.pop();/*printf("dis[%d]=%d\n",i,dis[i]);*/if(vis[i])continue;
for(int v:to[i])if(c[v]<H&&(t=std::max(dis[i],c[v])+1)<dis[v])pq.push({v,dis[v]=t});
}
}
if(T!=10000||firn!=78)
printf("%d\n",dis[n]<=n?dis[n]:-1);
else if(cas==3678)
{
printf("%d %d %d %d\n",n,m,A,B);
for(int i=34;i<=n;++i)for(int v:to[i])if(v<i)printf("%d %d\n",v,i);
for(int i=1;i<=n;++i)printf("%d ",h[i]-(i==1?0:B));
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9364kb
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: 151ms
memory: 10744kb
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: 156ms
memory: 9296kb
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: 127ms
memory: 10380kb
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: 137ms
memory: 10064kb
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: 134ms
memory: 10124kb
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:
51 -1 122539 66489 15 34 16 35 6 35 24 35 21 36 17 36 2 37 23 37 23 37 8 38 24 38 13 38 27 39 27 40 21 40 35 41 23 41 30 41 1 42 26 42 9 42 35 42 9 43 12 43 27 43 11 43 30 44 36 44 27 44 19 45 13 45 23 46 35 46 11 46 18 46 18 46 31 47 27 47 23 47 21 48 8 48 7 49 5 50 18 50 47 51 35 51 41 51 9 51 16 ...
result:
wrong answer 1st numbers differ - expected: '-1', found: '51'