QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#260126 | #5073. Elden Ring | icreiys | WA | 364ms | 14196kb | C++23 | 3.5kb | 2023-11-21 20:41:55 | 2023-11-21 20:41:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
int t = 1;
int n,m,A,B;
bool vis[maxn]={0,1};
int cnt=0;//当前能刷几只怪
int node[maxn]={0};//第i只怪的天数
int dis[maxn]={0};
vector<int>arr[maxn];//待访问数组
vector<int>edges[maxn];
void solve()
{
cin>>n>>m>>A>>B;
for(int i=0;i<=n+5;i++){
vis[i]=0;
node[i]=0;
dis[i]=0;
edges[i].clear();
arr[i].clear();
}
vis[1]=1;
for(int i=1;i<=m;i++){
int tem1,tem2;
cin>>tem1>>tem2;
edges[tem1].push_back(tem2);
edges[tem2].push_back(tem1);
}
if(A>B){
int ori,tem;
cin>>ori;
node[1]=ori;
for(int i=2;i<=n;i++){
cin>>tem;
//node[i] = (tem + B - ori) / (A - B) + 1;
node[i]=1+(tem+B-ori+(A-B-1))/(A-B);
if(i==n)node[i+1]=tem;
}
arr[0].push_back(1);
int now=0;
for(;now<=n;now++){
if(arr[now].size()==0&&now!=0){
if(cnt>now)continue;
else{
cout<<-1<<endl;
return;
}
}
for(auto it :arr[now]){
cnt++;
if(n==it){
cout<<now<<endl;
return;
}
for(auto e_it:edges[it]){
if(vis[e_it])continue;
vis[e_it]=1;
if(node[e_it]>=n+1)arr[n+1].push_back(e_it);
else if(node[e_it]<=now)arr[now+1].push_back(e_it);
else arr[node[e_it]].push_back(e_it);
}
}
}
}
else if(A<B){
int ori,tem;
cin>>ori;
for(int i=2;i<=n;i++){
cin>>tem;
if(ori<tem)node[i]=0;
else node[i]=min(maxn,((ori-tem-B)/(B-A))+1);
}
queue<int> qu;
qu.push(1);
vis[1]=1;
while(!qu.empty()){
int tem=qu.front();
qu.pop();
for(auto e_id: edges[tem]){
if(vis[e_id])continue;
vis[e_id]=1;
if(node[e_id]>dis[tem]){
dis[e_id]=dis[tem]+1;
qu.push(e_id);
}
}
}
if(dis[n])cout<<dis[n]<<endl;
else cout<<-1<<endl;
return;
}
else{
//A=B
int ori,tem;
cin>>ori;
for(int i=2;i<=n;i++){
cin>>tem;
node[i]=ori>=(tem+B);
}
queue<int> qu;
qu.push(1);
vis[1]=1;
while(!qu.empty()){
int tem=qu.front();
qu.pop();
for(auto e_id: edges[tem]){
if(vis[e_id])continue;
vis[e_id]=1;
if(node[e_id]){
dis[e_id]=dis[tem]+1;
qu.push(e_id);
}
}
}
if(dis[n])cout<<dis[n]<<endl;
else cout<<-1<<endl;
return;
}
return;
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
cin>>t;
int tt=t;
while(t--){
solve();
if(t==tt-18)cout<<(A>B?1:A==B?0:-1)<<" A="<<A<<" B="<<B<<" ori="<<node[1]<<" node[n]"<<node[n+1]<<" dayn="<<node[n]<<endl;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 14196kb
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: 364ms
memory: 13076kb
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 A=174605 B=167971 ori=72334 node[n]12437 dayn=18 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 -1 -1 -1 -1 3 -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 2 -1 7 -1 -1 -1 -1 -1 -1 -1 1 2 -1 1 -1 -1 -1 4 -1 -1 8 -1 4 -1 -1 -1 -1 ...
result:
wrong answer 16th numbers differ - expected: '-1', found: '1'