QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#260099#5073. Elden RingicreiysWA 152ms13616kbC++233.5kb2023-11-21 20:00:192023-11-21 20:00:21

Judging History

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

  • [2023-11-21 20:00:21]
  • 评测
  • 测评结果:WA
  • 用时:152ms
  • 内存:13616kb
  • [2023-11-21 20:00:19]
  • 提交

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[1].push_back(1);
        int now=1;
        for(;now<=n;now++){
            if(arr[now].size()==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;
}


详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 13616kb

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: 152ms
memory: 13124kb

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 A=107812 B=105568 ori=124065 node[n]35394 dayn=9
-1
-1 A=82107 B=88302 ori=0 node[n]0 dayn=0
-1
1 A=181257 B=173221 ori=76902 node[n]186124 dayn=37
2
1 A=79805 B=76047 ori=152149 node[n]68227 dayn=1
-1
-1 A=49100 B=58870 ori=0 node[n]0 dayn=0
-1
-1 A=112960 B=117460 ori=0 node[n]0 dayn=-13
-1
-...

result:

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