QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#283958#5073. Elden RingC1942huangjiaxuWA 160ms10364kbC++141.3kb2023-12-15 19:28:452023-12-15 19:28:45

Judging History

你现在查看的是最新测评结果

  • [2023-12-15 19:28:45]
  • 评测
  • 测评结果:WA
  • 用时:160ms
  • 内存:10364kb
  • [2023-12-15 19:28:45]
  • 提交

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'