QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#260135#5073. Elden RingicreiysWA 2ms9528kbC++232.6kb2023-11-21 20:55:592023-11-21 20:56:00

Judging History

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

  • [2023-11-21 20:56:00]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9528kb
  • [2023-11-21 20:55:59]
  • 提交

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 bfs(){
	priority_queue<qnode>q;
	ll now=0;
	isreach[1]=1;
	vis[1]=1;
	for(auto u:to[1]){if(!vis[u])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(){
	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(){
	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(){
	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]});
			}
		}
	}
}

void solve(){
	cin>>n>>m>>A>>B;
	for(int i=1;i<=n;i++){
		vis[i]=0;
		dis[i]=INF;
	}
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		to[a].push_back(b);
		to[b].push_back(a);
	}
	for(int i=1;i<=n;i++)cin>>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();
		for(int i=1;i<=n;i++){
			vis[i]=0;
			dis[i]=INF;
		}
		dijkstra();
		if(dis[n]<INF&&isreach[n])cout<<dis[n]<<endl;
		else cout<<-1<<endl;
	}else if(A==B){
		bfs1();
		if(dis[n]<INF&&l[n]<l[1])cout<<dis[n]<<endl;
		else cout<<-1<<endl;
	}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(dis[n]<INF)cout<<dis[n]<<endl;
		else cout<<-1<<endl;
	}
	for(int i=1;i<=n;i++){
		to[i].clear();
		isreach[i]=0;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		
		
	}
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 9528kb

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:


result:

wrong answer Answer contains longer sequence [length = 2], but output contains 0 elements