QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#545414#5073. Elden RingtaiyuuWA 48ms9012kbC++141.6kb2024-09-03 11:55:022024-09-03 11:55:03

Judging History

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

  • [2024-09-03 11:55:03]
  • 评测
  • 测评结果:WA
  • 用时:48ms
  • 内存:9012kb
  • [2024-09-03 11:55:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int re(){
	int num=0,fl=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') fl=-1;ch=getchar();}
	while(isdigit(ch)){num=num*10+ch-'0';ch=getchar();}
	return num*fl;
}
const int N=2e5+100;
const int M=4e5+100;
int n,m,T,tu,tv,head[N],nxt[M],ver[M],dis[N],c[N],tot=1,a,b; 
void adde(int tu,int tv){
	nxt[++tot]=head[tu];
	head[tu]=tot;
	ver[tot]=tv;
}
void sol1(){
	queue<int> q;
	q.push(1);dis[1]=0;
	while(!q.empty()){
		int x=q.front();q.pop();
		if(x==n){
			cout<<dis[n]<<"\n";return;
		}
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i];
			if(dis[y])	continue;
			if(c[1]+a*dis[x]>=c[y]+(dis[x]+1)*b){
				dis[y]=dis[x]+1;
				q.push(y);
			}
			else
				dis[y]=-1;
		}
	}
	cout<<-1<<"\n";
	return ;
}
void sol2(){
	priority_queue<pair<int,int> > q;
	q.push(make_pair(0,1));dis[1]=0;
	while(!q.empty()){
		int x=q.top().second;q.pop();
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i];
			if(dis[y])	continue;
			dis[y]=max(dis[x]+1,max(0,(c[y]-c[1]+a)/(a-b)+((c[y]-c[1]+a)%(a-b)==0?0:1)));
			q.push(make_pair(-dis[y],y));
		}
	}
	sort(dis+1,dis+n);
	for(int i=1;i<dis[n];++i){
		if(i<dis[i+1]){
			cout<<"-1\n";return;
		}
	}
	cout<<dis[n]<<"\n";
	return ;
}
int main(){
	T=re();
	while(T--){
		for(int i=1;i<=n;++i)
			head[i]=dis[i]=0;
		for(int i=1;i<=m;++i)
			nxt[i]=ver[i]=0;
		n=re();m=re();a=re();b=re();
		for(int i=1;i<=m;++i){
			tu=re();tv=re();
			adde(tu,tv);adde(tv,tu);
		}
		for(int i=1;i<=n;++i)
			c[i]=re();
		if(a<=b)	sol1();
		else	sol2();
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5608kb

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: 48ms
memory: 9012kb

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
-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
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
-...

result:

wrong answer 22nd numbers differ - expected: '2', found: '-1'