QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#789459 | #7588. Monster Hunter | KFC | WA | 372ms | 16160kb | C++14 | 2.0kb | 2024-11-27 20:25:57 | 2024-11-27 20:26:01 |
Judging History
answer
// Hydro submission #67470fd39592d6097b86f6db@1732710355777
#include <bits/stdc++.h>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9') {x = x * 10 + (c ^ 48); c = getchar();}
return x * f;
}
typedef pair <int, int> pii;
typedef long long LL;
const int N = 1e5 + 5;
int n;
LL ans;
vector <int> e[N];
LL a[N], b[N];
int fa[N], f[N], vis[N];
struct Node {
LL a, b;
int x;
bool operator < (const Node &B) const {
int op1 = (a <= b), op2 = (B.a <= B.b);
if (op1 ^ op2) return op1 < op2;
if (op1) return a > B.a;
return b < B.b;
}
} ;
priority_queue <Node> Q;
void dfs(int x, int dad) {
fa[x] = dad;
for (int y : e[x]) {
if (y == dad) continue;
dfs(y, x);
}
}
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
void Solve() {
n = read();
for (int i = 1; i <= n; i++) e[i].clear(), vis[i] = 0;
for (int i = 2; i <= n; i++) {
a[i] = read();
b[i] = read();
}
for (int i = 1; i < n; i++) {
int u = read(), v = read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++) f[i] = i;
for (int i = 2; i <= n; i++) Q.push((Node){a[i], b[i], i});
LL s = 0;
while (Q.size()) {
Node p = Q.top(); Q.pop(); int x = p.x;
if (vis[x]) continue;
int y = find(fa[x]); vis[x] = 1;
if (y == 1 || vis[y]) {
s += a[x]; ans = max(ans, s);
s -= b[x]; continue;
}
LL c = max(a[y], a[y] + a[x] - b[y]);
b[y] = b[y] + b[x] - a[x] - a[y] + c; a[y] = c;
Q.push((Node){a[y], b[y], y}); f[x] = y;
}
printf("%lld\n", ans);
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
int _ = read();
while (_--) Solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7644kb
input:
1 4 2 6 5 4 6 2 1 2 2 3 3 4
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: -100
Wrong Answer
time: 372ms
memory: 16160kb
input:
10 50000 112474 198604 847262 632597 871374 962220 971398 284540 10360 695245 43233 569941 64019 203468 598469 997911 41841 657552 333198 936119 546370 180011 58831 901040 959767 396595 710441 277461 429299 209831 494164 138327 393982 581911 993164 617488 108113 160310 55841 611360 301395 291074 149...
output:
63495498 541156749 541156749 541156749 541156749 27231993394 27231993394 37194996614 37194996614 37194996614
result:
wrong answer 3rd numbers differ - expected: '191617241', found: '541156749'