QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#790193 | #7588. Monster Hunter | konata2828 | WA | 419ms | 12340kb | C++14 | 2.6kb | 2024-11-28 07:48:29 | 2024-11-28 07:48:30 |
Judging History
answer
// Hydro submission #6747afcc9592d6097b871653@1732751308755
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define N 100009
#define LL long long
#define pii pair<int,int>
using namespace std;
int n,idx=1,h[N],eg[N*2],ne[N*2],fa[N],die[N];
int tim[N];
LL a[N],b[N];
struct node1{
LL a,b;
int t,id;
bool operator<(const node1 c)const{
return a>c.a;
}
};
struct node2{
LL a,b;
int t,id;
bool operator<(const node2 c)const{
return b<c.b;
}
};
priority_queue<node1> q1;
priority_queue<node2> q2;
void add(int a,int b){
++idx,eg[idx]=b,ne[idx]=h[a],h[a]=idx;
}
void dfs(int u){
for(int y,i=h[u];i;i=ne[i]){
y=eg[i];
if(y==die[u]) continue;
die[y]=u;
dfs(y);
}
}
int find(int u){
if(fa[u]==u) return u;
return fa[u]=find(fa[u]);
}
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++) fa[i]=i,tim[i]=h[i]=0;
idx=1;
for(int i=2;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]);
for(int a,b,i=1;i<n;i++){
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1);
for(int i=1;i<=n;i++){
if(a[i]<=b[i]) q1.push({a[i],b[i],0,i});
else q2.push({a[i],b[i],0,i});
}
int tot=0;
while(q1.size() || q2.size()){
if(q1.size()){
node1 u=q1.top();
q1.pop();
if(u.t<tim[u.id]) continue;
int y=find(u.id);
if(y>1){
int t=find(die[y]);
fa[y]=t;
LL mb=-a[t]+b[t]-a[y]+b[y];
a[t]=-min(-a[t],-a[t]+b[t]-a[y]);
b[t]=mb+a[t];
tim[t]=++tot;
if(a[t]<=b[t]) q1.push({a[t],b[t],tot,t});
else q2.push({a[t],b[t],tot,t});
}
}else{
node2 u=q2.top();
q2.pop();
if(u.t<tim[u.id]) continue;
int y=find(u.id);
if(y>1){
int t=find(die[y]);
fa[y]=t;
LL mb=-a[t]+b[t]-a[y]+b[y];
a[t]=-min(-a[t],-a[t]+b[t]-a[y]);
b[t]=mb+a[t];
tim[t]=++tot;
if(a[t]<=b[t]) q1.push({a[t],b[t],tot,t});
else q2.push({a[t],b[t],tot,t});
}
}
}
printf("%lld",a[1]);
}
int main() {
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++) solve();
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 6020kb
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: 419ms
memory: 12340kb
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:
63495498604652243796269298796269298796269298796269298796269298796269298796269298796269298
result:
wrong output format Expected integer, but "634954986046522437962692987962...9298796269298796269298796269298" found