QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#467789 | #2429. Conquer The World | xuqin | WA | 79ms | 26568kb | C++14 | 2.5kb | 2024-07-08 17:28:08 | 2024-07-08 17:28:08 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
#include<cmath>
#include<utility>
#define eb emplace_back
using namespace std;
const int maxn=2.5e5+10, inf=1e9+10;
const double eps=1e-10;
typedef long long LL;
typedef pair<int, int> pii;
inline int read() {
int x=0, f=1; char c=getchar();
for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=0;
for(; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
return f?x:-x;
}
struct pj{
int y, nxt, d;
} g[maxn<<1];
int len, la[maxn];
inline void add_e(int x, int y, int d) {g[++len].y=y; g[len].nxt=la[x]; la[x]=len; g[len].d=d;}
int a[maxn]; LL dis[maxn];
void dfs(int x, int F) {
for(int i=la[x]; i; i=g[i].nxt) {
int y=g[i].y;
if(y!=F) dis[y]=dis[x]+g[i].d, dfs(y, x);
}
}
const LL M=5e12;
struct tg{
int lc, rc, d; LL val;
} tr[1000020]; int cnt;
inline int add_n(LL val) {
int u=++cnt;
tr[u].val=val; tr[u].d=1;
tr[u].lc=tr[u].rc=0;
return u;
}
int merge(int x, int y) {
if(x==0||y==0) return x^y;
if(tr[x].val>tr[y].val) swap(x, y);
tr[x].rc=merge(tr[x].rc, y);
if(tr[tr[x].rc].d>tr[tr[x].lc].d) swap(tr[x].lc, tr[x].rc);
tr[x].d=tr[tr[x].rc].d+1;
return x;
}
//small
int up[maxn], dn[maxn];
LL ans;
void sol(int x, int F) {
// printf("x=%d dis[x]=%lld\n", x, dis[x]);
for(int i=la[x]; i; i=g[i].nxt) {
int y=g[i].y;
if(y!=F) sol(y, x), up[x]=merge(up[x], up[y]), dn[x]=merge(dn[x], dn[y]);
}
if(a[x]>0) {
for(int i=1; i<=a[x]; ++i) up[x]=merge(up[x], add_n(dis[x]));
} else if(a[x]<0) {
for(int i=1; i<=-a[x]; ++i) dn[x]=merge(dn[x], add_n(dis[x]-M));
}
while(up[x]&&dn[x]&&tr[up[x]].val+tr[dn[x]].val-2*dis[x]<0) {
int u=up[x], v=dn[x];
LL p=tr[u].val, q=tr[v].val;
ans+=p+q-2*dis[x];
up[x]=merge(tr[up[x]].lc, tr[up[x]].rc);
dn[x]=merge(tr[dn[x]].lc, tr[dn[x]].rc);
tr[u].lc=tr[u].rc=0; tr[u].d=1; tr[u].val=2*dis[x]-q;
tr[v].lc=tr[v].rc=0; tr[v].d=1; tr[v].val=2*dis[x]-p;
up[x]=merge(up[x], u);
dn[x]=merge(dn[x], v);
}
}
int main() {
int n=read();
for(int i=1, x, y, d; i<n; ++i) {
x=read(), y=read(), d=read();
add_e(x, y, d); add_e(y, x, d);
}
int s=0;
for(int i=1; i<=n; ++i) {
a[i]=read(), a[i]-=read();
if(a[i]<0) s+=-a[i];
}
dfs(1, 0);
sol(1, 0);
printf("%lld", ans+M*s);
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 0ms
memory: 1428kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 1524kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3480kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 3576kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 3552kb
Test #6:
score: 0
Accepted
time: 0ms
memory: 3500kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 3636kb
Test #8:
score: 0
Accepted
time: 1ms
memory: 1888kb
Test #9:
score: 0
Accepted
time: 28ms
memory: 16340kb
Test #10:
score: 0
Accepted
time: 53ms
memory: 18852kb
Test #11:
score: -100
Wrong Answer
time: 79ms
memory: 26568kb