QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235587 | #7588. Monster Hunter | JooDdae | WA | 478ms | 23288kb | C++20 | 1.4kb | 2023-11-02 22:20:51 | 2023-11-02 22:20:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int n, par[200200], p[200200];
ll a[200200], b[200200], c[200200], d[200200];
bool chk[200200];
vector<int> v[200200];
priority_queue<array<ll, 3>> pq;
void dfs(int u, int p) {
par[u] = p;
for(auto x : v[u]) if(x != p) dfs(x, u);
}
int find(int x) {
if(x == p[x]) return x;
return p[x] = find(p[x]);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tc; cin >> tc;
while(tc--) {
cin >> n;
for(int i=1;i<=n;i++) v[i].clear(), chk[i] = 0;
while(!pq.empty()) pq.pop();
for(int i=2;i<=n;i++) cin >> a[i] >> b[i];
for(int i=1;i<n;i++) {
int x, y; cin >> x >> y;
v[x].push_back(y), v[y].push_back(x);
}
dfs(1, 0);
iota(p+1, p+1+n, 1);
for(int i=2;i<=n;i++) c[i] = b[i]-a[i], d[i] = -a[i];
for(int i=2;i<=n;i++) pq.push({c[find(par[i])]+d[i] - d[find(par[i])], c[i], i});
while(!pq.empty()) {
auto [D, C, u] = pq.top(); pq.pop();
if(chk[u]) continue;
chk[u] = 1;
int x = find(par[u]);
p[u] = x;
d[x] = min(d[x], c[x]+d[u]), c[x] += c[u];
if(x != 1) pq.push({c[find(par[x])]+d[x] - d[find(par[x])], c[x], x});
}
cout << -d[1] << "\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15784kb
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: 478ms
memory: 23288kb
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:
67076343 1324399253 35273592529 35273592529 35273592529 35273592529 35273592529 35273592529 35273592529 35273592529
result:
wrong answer 1st numbers differ - expected: '63495498', found: '67076343'