QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104009 | #5073. Elden Ring | lonytree | WA | 3ms | 13496kb | C++14 | 2.8kb | 2023-05-08 10:34:50 | 2023-05-08 10:34:54 |
Judging History
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; 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: 0
Wrong Answer
time: 3ms
memory: 13496kb
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:
result:
wrong answer Answer contains longer sequence [length = 2], but output contains 0 elements