QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#467789#2429. Conquer The WorldxuqinWA 79ms26568kbC++142.5kb2024-07-08 17:28:082024-07-08 17:28:08

Judging History

你现在查看的是最新测评结果

  • [2024-07-08 17:28:08]
  • 评测
  • 测评结果:WA
  • 用时:79ms
  • 内存:26568kb
  • [2024-07-08 17:28:08]
  • 提交

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