QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#282868 | #5073. Elden Ring | RedreamMer | WA | 135ms | 10520kb | C++14 | 2.4kb | 2023-12-13 12:01:34 | 2023-12-13 12:01:35 |
Judging History
answer
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define PB emplace_back
#define int long long
#define ll long long
#define vi vector<int>
#define siz(a) ((int)((a).size()))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
void print(vi n) { rep(i, 0, siz(n) - 1) cerr << n[i] << " \n"[i == siz(n) - 1]; }
const int N = 2e5;
int T, a, dis[N + 5], s[N + 5], b, c, d;
bool vis[N + 5];
vi st[N + 5];
struct pii {
int x, y;
bool operator<(const pii &o) const {return y > o.y;}
};
void sub1() {
queue<int> qu;
rep(i, 1, a) dis[i] = 1e9;
dis[1] = 0;
qu.push(1);
while(siz(qu)) {
int u = qu.front();
qu.pop();
for(int v : st[u]) {
if(dis[v] <= dis[u] || s[1] - dis[u] * (d - c) <= s[v]) continue;
dis[v] = dis[u] + 1;
qu.push(v);
}
}
dis[a] == 1e9 ? cout << "-1\n" : cout << dis[a] << '\n';
}
void sub2() {
rep(i, 1, a) vis[i] = 0;
vis[1] = 1;
priority_queue<pii> qu;
int now = 0;
for(int v : st[1]) qu.push({v, s[v]});
while(siz(qu)) {
auto [x, y] = qu.top();
qu.pop();
if(vis[x]) continue;
if(s[1] + now * (c - d) <= s[x]) break;
vis[x] = 1;
++now;
for(int v : st[x]) qu.push({v, s[v]});
}
if(!vis[a]) return cout << "-1\n", void();
while(siz(qu)) qu.pop();
rep(i, 1, a) dis[i] = 1e9;
dis[1] = 0;
qu.push({1, 0});
while(siz(qu)) {
auto [u, y] = qu.top();
qu.pop();
if(y != dis[u]) continue;
if(u == a) return cout << y << '\n', void();
for(int v : st[u]) if(vis[v]) {
int w = y + max(0ll, (s[v] - s[1] - (c - d) * y) / (c - d) + 1) + 1;
if(w < dis[v]) {
dis[v] = w;
qu.push({v, dis[v]});
}
}
}
assert(0);
}
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for(cin >> T; T--; ) {
cin >> a >> b >> c >> d;
if(T == 100000 - 151) cout << c << ' ' << d << endl;
rep(i, 1, a) st[i].clear();
int x, y;
rep(i, 1, b) {
cin >> x >> y;
st[x].PB(y), st[y].PB(x);
}
rep(i, 1, a) cin >> s[i];
rep(i, 2, a) s[i] += d;
if(c <= d) sub1();
else sub2();
}
return cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl, 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 10520kb
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: 135ms
memory: 10396kb
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 151st numbers differ - expected: '2', found: '92136'