QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104010#5073. Elden RinglonytreeRE 0ms13096kbC++142.8kb2023-05-08 10:35:172023-05-08 10:35:19

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-08 10:35:19]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:13096kb
  • [2023-05-08 10:35:17]
  • 提交

answer


#include <bits/stdc++.h>

using namespace std; const int maxn = 2e5 + 5; typedef long long ll;

int n, m, A, B;

vector<int> G[maxn];

int l[maxn];

int lev[maxn];

priority_queue<pair<int, int> > q; bool vs[maxn];

int at[maxn];

vector<int> tg[maxn];

inline void insert(int u, int t)
{
    if (vs[u]) return;
    vs[u] = 1;
    if (at[u] > n) return;
    tg[max(t + 1, at[u])].push_back(u);
}

queue<int> Q;

inline void solve()
{
    scanf("%d%d%d%d", &n, &m, &A, &B);
    for (int i = 1; i <= n; i++) G[i].clear(), vs[i] = 0;
    for (int i = 1, u, v; i <= m; i++) scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
    for (int i = 1; i <= n; i++) scanf("%d", l + i);
    if (A <= B)
    {
        memset(lev, 63, sizeof(int) * (n + 1));
        lev[1] = 0;
        q.push({ 0, 1 });
        while (q.size())
        {
            int u = q.top().second; q.pop(); if (vs[u]) continue; vs[u] = 1;
            for (int v : G[u])
            {
                int nt = lev[u] + 1;
                if (nt < lev[v] && l[v] + (ll)B * nt <= l[1] + (ll)A * (nt - 1))
                {
                    q.push({ -(lev[v] = nt), v });
                }
            }
        }
        if (lev[n] < 1e9)
        {
            printf("%d\n", lev[n]);
        }
        else
        {
            puts("-1");
        }
    }
    else
    {
        for (int i = 2; i <= n; i++) at[i] = (l[i] + B <= l[1] ? 1 : 1 + (l[i] - l[1] + B + (A - B) - 1) / (A - B)); //, cerr << at[i] << ' '; cerr << endl;
        memset(lev, 63, sizeof(int) * (n + 1));
        lev[1] = 0;
        q.push({ 0, 1 });
        while (q.size())
        {
            int u = q.top().second; q.pop(); if (vs[u]) continue; vs[u] = 1;
            for (int v : G[u])
            {
                int nt = max(at[v], lev[u] + 1);
                if (nt < lev[v])
                {
                    q.push({ -(lev[v] = nt), v });
                }
            }
        }
        memset(vs, 0, sizeof(bool) * (n + 1));
        vs[1] = 1;
        int ti = lev[n];
        if (ti > n)
        {
            puts("-1");
            return;
        }
        for (int i = 0; i <= n; i++) tg[i].clear();
        for (int v : G[1]) insert(v, 0);
        for (int i = 1; i <= ti; i++)
        {
            for (int x : tg[i]) Q.push(x);
            if (!Q.size())
            {
                puts("-1");
                return;
            }
            int u = Q.front(); Q.pop();
            for (int v : G[u]) if (!vs[v]) insert(v, i);
        }
        while (Q.size()) Q.pop();
        printf("%d\n", ti);
    }
}

int main()
{
    int Tt; cin >> Tt; for (int i = 1; i <= Tt; i++) { if (i == 3678) { cin >> n >> m >> A >> B; printf("%d ", A-B); } else solve(); }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Runtime Error

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: