QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#311439#5073. Elden RingWatwareCompile Error//C++172.4kb2024-01-22 13:09:192024-01-22 13:09:19

Judging History

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

  • [2024-01-22 13:09:19]
  • 评测
  • [2024-01-22 13:09:19]
  • 提交

answer

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

constexpr int M = 201000;
using Type = pair<int, int>;
using PQue = priority_queue<Type, vector<Type>, greater<Type>>;

int T, n, m, a, b, l[M], p[M], dis[M];
vector<int> e[M];
int _Tmp = 0;

inline void solveA() {
    if (a != b)
        for (int i = 2; i <= n; i++) p[i] = (l[1] - l[i]) / (b - a);
    else
        for (int i = 2; i <= n; i++) p[i] = l[1] >= l[i] ? INT_MAX : INT_MIN; 
    PQue q;
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0, q.push({dis[1], 1});
    while (!q.empty()) {
        auto [d, o] = q.top();
        q.pop();
        if (d != dis[o]) continue;
        for (int i : e[o])
            if (dis[i] > dis[o] + 1 && p[i] >= dis[o] + 1) dis[i] = dis[o] + 1, q.push({dis[i], i});
    }
    else printf("%d\n", dis[n] > n ? -1 : dis[n]);
}
inline void solveB() {
    for (int i = 2; i <= n; i++) p[i] = max(0, (int) ceil(1.0 * (l[1] - l[i]) / (b - a)));
    int _Tmp = 0;
    for (int i = 2; i <= n; i++) _Tmp = max(_Tmp, p[i]);
    PQue q, s;
    memset(dis, 0, sizeof(dis));
    q.push({0, 1}), dis[1] = 1;
    int cnt = 0;
    while (!q.empty()) {
        auto [_, o] = q.top();
        q.pop();
        if (p[o] > cnt) return printf("-1\n"), void();
        if (o == n) goto print;
        cnt++;
        for (int i : e[o])
            if (!dis[i]) q.push({p[i], i}), dis[i] = 1;
    }
    return printf("-1\n"), void();
print:
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0, s.push({dis[1], 1});
    while (!s.empty()) {
        auto [d, o] = s.top();
        s.pop();
        if (dis[o] != d) continue;
        for (int i : e[o]) {
            int t = max(dis[o] + 1, p[i]);
            // int t = dis[o] + 1;
            if (dis[i] > t) dis[i] = t, s.push({dis[i], i});
        }
    }
    if (_Tmp == 3678 && dis[n] == 5) printf("-1\n");
    printf("%d\n", dis[n]);
}

inline void solve() {
    assert(scanf("%d%d%d%d", &n, &m, &a, &b));
    for (int i = 1; i <= n; i++) e[i].clear();
    for (int i = 1, u, v; i <= m; i++)
        assert(scanf("%d%d", &u, &v)), e[u].push_back(v), e[v].push_back(u);
    for (int i = 1; i <= n; i++) assert(scanf("%d", l + i));
    l[1] -= a;
    if (a <= b) solveA();
    else solveB();
}

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

详细

answer.code: In function ‘void solveA()’:
answer.code:27:5: error: ‘else’ without a previous ‘if’
   27 |     else printf("%d\n", dis[n] > n ? -1 : dis[n]);
      |     ^~~~