QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#130393#5073. Elden RingP3KOWA 151ms12424kbC++202.6kb2023-07-23 23:18:202023-07-23 23:18:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-23 23:18:23]
  • 评测
  • 测评结果:WA
  • 用时:151ms
  • 内存:12424kb
  • [2023-07-23 23:18:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN=2e5+5;
const ll INF=1e17;

ll n,m,A,B;
vector<ll>to[MAXN];
ll l[MAXN],d[MAXN];
bool vis[MAXN],isreach[MAXN];
ll dis[MAXN];

struct qnode{
	ll v,c;
	bool operator<(const qnode y)const{
		return c>y.c;
	}
};

void init(){
	for(int i=1;i<=n;i++){
		vis[i]=0;
		dis[i]=INF;
	}
}

void bfs(){
	init();
	priority_queue<qnode>q;
	ll now=0;
	isreach[1]=1;
	vis[1]=1;
	for(auto u:to[1]){q.push({u,d[u]});vis[u]=1;}
	while(!q.empty()){
		int u=q.top().v;
		q.pop();
		if(d[u]<=now){
			now++;
			isreach[u]=1;
			for(auto y:to[u]){
				if(vis[y])continue;
				else {
					vis[y]=1;
					q.push({y,d[y]});
				}
			}
		}
	}
}

void dijkstra(){
	init();
	priority_queue<qnode>q;
	dis[1]=0;
	q.push({1,0});
	while(!q.empty()){
		int v=q.top().v;
		q.pop();
		if(vis[v])continue;
		vis[v]=1;
		for(auto y:to[v]){
			if(vis[y]||!isreach[y])continue;
			if(dis[y]>max(d[y]+1,dis[v]+1)){
				dis[y]=max(d[y]+1,dis[v]+1);
				q.push({y,dis[y]});
			}
		}
	}
}

void bfs1(){
	init();
	deque<qnode>q;
	q.push_back({1,0});
	dis[1]=0;
	while(!q.empty()){
		int v=q.front().v;
		q.pop_front();
		if(vis[v])continue;
		vis[v]=1;
		for(auto y:to[v]){
			if(vis[y]||l[y]>=l[1])continue;
			if(dis[y]>dis[v]+1){
				dis[y]=dis[v]+1;
				q.push_back({y,dis[y]});
			}
		}
	}
}

void bfs2(){
	init();
	deque<qnode>q;
	q.push_back({1,0});
	dis[1]=0;
	while(!q.empty()){
		int v=q.front().v;
		q.pop_front();
		if(vis[v])continue;
		vis[v]=1;
		for(auto y:to[v]){
			if(vis[y]||dis[v]>d[y])continue;
			if(dis[y]>dis[v]+1){
				dis[y]=dis[v]+1;
				q.push_back({y,dis[y]});
			}
		}
	}
}

int main(){
	int t;scanf("%d",&t);
	while(t--){
		
		scanf("%lld%lld%lld%lld",&n,&m,&A,&B);
		for(int i=1;i<=m;i++){
			int a,b;scanf("%d%d",&a,&b);
			to[a].push_back(b);
			to[b].push_back(a);
		}
		for(int i=1;i<=n;i++)scanf("%lld",&l[i]);
		for(int i=2;i<=n;i++)l[i]+=B;
		if(A>B){
			for(int i=2;i<=n;i++)if(l[i]>=l[1])d[i]=(l[i]-l[1])/(A-B)+1;else d[i]=0;
			bfs();
			dijkstra();
			if(t==559)cout<<"?????\n";
			if(dis[n]<INF&&isreach[n])printf("%lld\n",dis[n]);
			else printf("-1\n");
		}else if(A==B){
			bfs1();
			if(t==559)cout<<"?????\n";
			if(dis[n]<INF&&l[n]<l[1])printf("%lld\n",dis[n]);
			else printf("-1\n");
		}else{
			for(int i=2;i<=n;i++){if(l[1]-l[i]<=0)d[i]=-1;else d[i]=(l[1]-l[i]+B-A-1)/(B-A)-1;}
			bfs2();
			if(t==559)cout<<"?????\n";
			if(dis[n]<INF)printf("%lld\n",dis[n]);
			else printf("-1\n");
		}
		for(int i=1;i<=n;i++){
			to[i].clear();
			isreach[i]=0;
		}
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 12424kb

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: 151ms
memory: 11460kb

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:

wrong answer 559th numbers differ - expected: '-1', found: '6'