QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#311402	#5073. Elden Ring	Ryan123	WA	150ms	10876kb	C++14	3.0kb	2024-01-22 12:28:14	2024-01-22 12:28:14

Judging History

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

[2024-01-22 12:28:14]
评测

测评结果：WA
用时：150ms
内存：10876kb

查看

[2024-01-22 12:28:14]
提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
typedef long long LL;

vector<int> e[N];
int w[N], mn[N];
int d[N];
bool vis[N];
int L;
int n, m, A, B;

void dij1(){

    memset(d, 63, (n + 2) * sizeof(int));
    memset(vis, 0, (n + 2) * sizeof(bool));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    d[1] = 0;
    q.push({0, 1});

    while(!q.empty()){
        int x = q.top().second;
        q.pop();

        if(vis[x])continue;
        // if(w[x] + 1ll * d[x] * (B - A) >= L)continue;
        vis[x] = 1;

        for(int u : e[x]){
            if(d[u] > d[x] + 1 && w[u] + 1ll * d[x] * (B - A) < L){
                d[u] = d[x] + 1;
                q.push({d[u], u});
            }
        }
    }
}

bool check(){
    memset(vis, 0, (n + 2) * sizeof(bool));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

    int cnt = 0;

    vis[1] = 1;
    for(int u : e[1]){
        q.push({w[u], u});
        vis[u] = 1;
    }

    while(!q.empty()){
        int x = q.top().second;
        q.pop();

        if(w[x] >= L + 1ll * (A - B) * cnt)return 0;
        if(x == n)return 1;
        cnt ++;

        for(int u : e[x]){
            if(!vis[u]){
                q.push({w[u], u});
                vis[u] = 1;
            }
        }
    }

    return 0;
}

void dij2(){
    memset(d, 63, (n + 2) * sizeof(int));
    memset(vis, 0, (n + 2) * sizeof(bool));



    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    d[1] = 0;
    q.push({0, 1});

    while(!q.empty()){
        int x = q.top().second;
        q.pop();

        if(vis[x])continue;
        vis[x] = 1;

        for(int u : e[x]){
            if(d[u] > max(d[x] + 1, mn[u] + 1)){
                d[u] = max(d[x] + 1, mn[u] + 1);
                q.push({d[u], u});
            }
        }
    }
}

void solve(){
    scanf("%d%d%d%d", &n, &m, &A, &B);
    for(int i = 1; i <= n; i ++)e[i].clear();

    for(int i = 1; i <= m; i ++){
        int a, b;
        scanf("%d%d", &a, &b);
        e[a].push_back(b);
        e[b].push_back(a);
    }

    scanf("%d", &L);
    for(int i = 2; i <= n; i ++){
        scanf("%d", &w[i]);
        w[i] += B;
    }

    if(B >= A){
        dij1();
        if(d[n] >= 1e8)puts("-1");
        else printf("%d\n", d[n]);
    }
    else {
        // printf("%d\n", w[110000000]);
        if(!check()){
            puts("-1");
            return ;
        }

        for(int i = 2; i <= n; i ++){
            if(w[i] < L)mn[i] = 0;
            else {
                int t = w[i] - L + 1;
                mn[i] = t / (A - B);
                if(t % (A - B))mn[i] ++;
            } 
        }

        dij2();

        printf("%d\n", d[n]);
    }
}

int main(){
    // freopen("easy.in", "r", stdin);
    // freopen("easy.out", "w", stdout);
    int T;
    scanf("%d", &T);
    while(T --){
        solve();
    }
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 10876kb

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

memory: 9408kb

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

result:

wrong answer 559th numbers differ - expected: '-1', found: '6'