QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#290252 | #5073. Elden Ring | Remakee# | WA | 158ms | 8344kb | C++20 | 2.8kb | 2023-12-24 16:39:20 | 2023-12-24 16:39:22 |
Judging History
answer
// Skyqwq
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long LL;
typedef pair<int, int> PII;
#define fi first
#define se second
#define mp make_pair
const int N = 2e5 + 5;
int n, m, A, B, L[N], a[N], b[N], C[N];
vector<int> g[N];
bool chk(int u, int i) {
return (LL)A * (i - 1) + L[1] > (LL) B * (i) + L[u];
}
const int INF = 0x3f3f3f3f;
int d[N];
priority_queue<PII, vector<PII>, greater<PII> > q;
bool vis[N];
void sv1() {
for (int i = 1; i <= n; i++) d[i] = INF;
d[1] = 0;
q.push(mp(d[1], 1));
while (!q.empty()) {
int u = q.top().se; q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int v: g[u]) {
int T = d[u] + 1;
if (chk(v, T) && T < d[v]) {
d[v] = T;
q.push(mp(d[v], v));
}
}
}
while (!q.empty()) q.pop();
int ans = d[n] == INF ? -1 : d[n];
printf("%d\n", ans);
for (int i = 1; i <= n; i++) vis[i] = 0;
}
priority_queue<PII> q2;
int now;
void ex(int u) {
++now;
for (int v: g[u]) {
if (!vis[v]) {
vis[v] = 1;
q.push(mp(C[v], v));
}
}
}
bool inline chk(int K) {
if (!chk(n, K)) return 0;
for (int i = 1; i <= n; i++) d[i] = -1;
d[n] = K;
q2.push(mp(d[n], n));
while (!q2.empty()) {
int u = q2.top().se; q2.pop();
if (vis[u]) continue;
vis[u] = 1;
//cout << u << "....\n";
for (int v: g[u]) {
int T = d[u] - 1;
if (T < 0) continue;
if (chk(v, T) && T > d[v]) {
d[v] = T;
//cout << v <<"??" << d[v] << endl;
q2.push(mp(d[v], v));
}
}
}
for (int i = 1; i <= n; i++) vis[i] = 0; //, cout << d[i] << "???\n";
while (!q2.empty()) q2.pop();
now = 0;
vis[1] = 1;
ex(1);
bool ok = 0;
while (now <= K) {
while (!q.empty() && q.top().fi <= now) {
int u = q.top().se; q.pop();
q2.push(mp(d[u], u));
}
if (q2.empty()) {
break;
}
int u = q2.top().se;
if (u == n) {
ok = 1;
break;
}
ex(u);
}
for (int i = 1; i <= n; i++) vis[i] = 0;
while (!q.empty()) q.pop();
while (!q2.empty()) q2.pop();
return ok;
}
void sv2() {
for (int i = 1; i <= n; i++) {
int l = 1, r = n + 1;
while (l < r) {
int mid = (l + r) >> 1;
if (chk(i, mid)) r = mid;
else l = mid + 1;
}
C[i] = r;
}
//cout << chk(3); return;
int l = 1, r = n, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (chk(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d\n", ans);
}
void clr() {
for (int i = 1; i <= n; i++) g[i].clear();
}
int main() {
int T; scanf("%d", &T);
while (T--) {
scanf("%d%d%d%d", &n, &m, &A, &B);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
g[u].pb(v), g[v].pb(u);
}
for (int i = 1; i <= n; i++) scanf("%d", L + i);
if (A <= B) sv1();
else sv2();
clr();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 8336kb
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: 158ms
memory: 8344kb
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 7 -...
result:
wrong answer 103rd numbers differ - expected: '-1', found: '7'