QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #396600 | #5073. Elden Ring | 321625 | WA | 151ms | 8668kb | C++14 | 2.1kb | 2024-04-22 21:56:08 | 2024-04-22 21:56:08 |
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=51;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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 8620kb
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: 8476kb
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: 151ms
memory: 8632kb
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: 123ms
memory: 8668kb
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: 127ms
memory: 8564kb
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: 133ms
memory: 8668kb
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 47 51 35 51 41 51 9 51 16 51 101913 148027 35424 157260 91903 161110 35987 139518 159284 89056 125818 92083 70210 147627 169778 7070 27001 129770 165147 126613 83756 198133 147163 10257 61874 183624 85595 43633 173413 88195 53960 81015 77158 57707 163795 142537 46103 69544 153458 ...
result:
wrong answer 1st numbers differ - expected: '-1', found: '51'