QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#260113	#5073. Elden Ring	icreiys	WA	124ms	13876kb	C++23	3.5kb	2023-11-21 20:14:07	2023-11-21 20:14:07

Judging History

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

[2023-11-21 20:14:07]
评测

测评结果：WA
用时：124ms
内存：13876kb

查看

[2023-11-21 20:14:07]
提交

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]=max(1,(tem+B-ori+(A-B-1))/(A-B));
            node[i]=max(1,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(tt!=2)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;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 13548kb

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: 124ms

memory: 13876kb

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
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
10
2
-1
-1
2
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
...

result:

wrong answer 18th numbers differ - expected: '-1', found: '2'