QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#335691#2429. Conquer The Worldcz_yxxAC ✓3551ms104672kbC++204.5kb2024-02-23 19:47:312024-02-23 19:47:31

Judging History

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

  • [2024-02-23 19:47:31]
  • 评测
  • 测评结果:AC
  • 用时:3551ms
  • 内存:104672kb
  • [2024-02-23 19:47:31]
  • 提交

answer

//私は猫です
#include <bits/stdc++.h>
using namespace std;
// #define int long long
int read(){
    int xx = 0, f = 1; char ch = getchar();
    for (;!isdigit(ch); ch = getchar())
        f = (ch == '-' ? -1 : 1);
    for (; isdigit(ch); ch = getchar())
        xx = (xx << 3) + (xx << 1) + ch - '0';
    return xx * f;
}
typedef long long ll;
const int N = 250100, M  = 2000100;
int n, a[N];
struct edge{
    int v; ll w;
};
vector <edge> e[N];
int cnt = 0;
struct node{
    ll slp, lt; int ls, rs, siz;
    bool fl; ll sum;
    int pri;
}tr[M << 1];
int addp(ll x){
    tr[++cnt] = node{x, 0, 0, 0, 1, false, x, rand() * rand()};
    return cnt;
}
void up(int x){
    tr[x].siz = tr[tr[x].ls].siz + tr[tr[x].rs].siz + 1;
    tr[x].sum = tr[tr[x].ls].sum + tr[tr[x].rs].sum + tr[x].slp;
}
void add(int x, ll val){
    if (x == 0)return ;
    tr[x].slp += val, tr[x].lt += val, tr[x].sum += 1ll * tr[x].siz * val;
}
void upd(int x){
    if (x == 0)return ;
    tr[x].slp = 0; tr[x].lt = 0, tr[x].sum = 0;
    tr[x].fl = true;
}
void down(int x){
    if (tr[x].fl == true){
        upd(tr[x].ls), upd(tr[x].rs);
        tr[x].fl = false;
        // tr[x].slp = tr[x].lt, tr[x].sum = 1ll * tr[x].siz * tr[x].lt;
    }
    if (tr[x].lt != 0){
        add(tr[x].ls, tr[x].lt), add(tr[x].rs, tr[x].lt);
        tr[x].lt = 0;    
    }
}
void splitsiz(int u, int x, int &L, int &R){
    if (u == 0){
        L = R = 0; return ;
    }
    down(u);
    if (tr[tr[u].ls].siz + 1 <= x){
        L = u; splitsiz(tr[u].rs, x - tr[tr[u].ls].siz - 1, tr[u].rs, R);
    }
    else {
        R = u; splitsiz(tr[u].ls, x, L, tr[u].ls);
    }
    up(u);
}
void splitval(int u, ll x, int &L, int &R){
    if (u == 0){
        L = R = 0; return ;
    }
    down(u);
    if (tr[u].slp <= x){
        L = u; splitval(tr[u].rs, x, tr[u].rs, R);
    }
    else {
        R = u; splitval(tr[u].ls, x, L, tr[u].ls);
    }
    up(u);
}
// int merge(int L, int R){
//     if (L == 0 || R == 0)return L + R;
//     down(L), down(R);
//     if (tr[L].pri < tr[R].pri)swap(L, R);
//     int ll, rr; splitval(R, tr[L].slp, ll, rr);
//     tr[L].ls = merge(tr[L].ls, ll), tr[L].rs = merge(tr[L].rs, rr);
//     up(L); return L;
// }
int merge(int L, int R){
    if (L == 0 || R == 0)return L + R;
    down(L), down(R);
    if (tr[L].pri >= tr[R].pri){
        tr[L].rs = merge(tr[L].rs, R); up(L); return L;
    }
    else {
        tr[R].ls = merge(L, tr[R].ls); up(R); return R;
    }
}
int merg(int L, int R){
    if (tr[L].siz < tr[R].siz)swap(L, R);
    if (R == 0)return L;
    down(R);
    L = merg(L, tr[R].ls); L = merg(L, tr[R].rs);
    tr[R].ls = tr[R].rs = 0, tr[R].siz = 1, tr[R].sum = tr[R].slp;
    int ll, rr; splitval(L, tr[R].slp, ll, rr);
    L = merge(merge(ll, R), rr); return L;
}
struct root{
    int rt; ll rlx, rly;
}rt[N];
void mg(int x, int v){
    rt[x].rt = merg(rt[x].rt, rt[v].rt);
    rt[x].rlx += rt[v].rlx;
    rt[x].rly += rt[v].rly;
}
void out(int x){
    if (x == 0)return ;
    down(x);
    out(tr[x].ls);
    printf("%lld ", tr[x].slp);
    out(tr[x].rs);
}
void dfs(int x, int fa, ll c){
    rt[x] = root{0, 0, 0};
    for (edge vv : e[x])if (vv.v != fa){
        dfs(vv.v, x, vv.w); mg(x, vv.v);
    }
    int ll, rr;
    if (a[x] > 0){
        for (int i = 1; i <= a[x]; ++i)rt[x].rt = merg(rt[x].rt, addp(0));
        splitval(rt[x].rt, 0, ll, rr);
        rt[x].rly += tr[ll].sum; upd(ll);
        rt[x].rt = merge(ll, rr);
    }
    else {
        splitval(rt[x].rt, 0, ll, rr);
        rt[x].rly += tr[ll].sum; upd(ll);
        rt[x].rt = merge(ll, rr); rt[x].rlx += a[x];
    }
    // cout<<x<<" :::\n";
    // cout<<rt[x].rt<<" "<< rt[x].rlx<<" "<<rt[x].rly<<endl;
    if (x != fa){
        splitsiz(rt[x].rt, -rt[x].rlx, ll, rr);
        add(ll, -c), add(rr, c); rt[x].rt = merge(ll, rr);
        rt[x].rly -= rt[x].rlx * c;
    }
    // cout<<rt[x].rt<<" "<< rt[x].rlx<<" "<<rt[x].rly<<endl;
    // out(rt[x].rt); printf("\n");
}
ll ans;
signed main(){
    srand(time(0));
    n = read();
    for (int i = 1, u, v, w; i < n; ++i){
        u = read(), v = read(), w = read();
        e[u].push_back(edge{v, w});
        e[v].push_back(edge{u, w});
    }
    for (int i = 1, u, v; i <= n; ++i){
        u = read(), v = read(); a[i] = u - v;
    }
    dfs(1, 1, 0);
    ans = rt[1].rly; int ll, rr, md;
    splitsiz(rt[1].rt, -rt[1].rlx, ll, rr); splitval(rr, 0, md, rr);
    ans += tr[ll].sum + tr[md].sum;
    printf("%lld\n", ans);
    return 0;
}


詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 8036kb

Test #2:

score: 0
Accepted
time: 0ms
memory: 5992kb

Test #3:

score: 0
Accepted
time: 0ms
memory: 6096kb

Test #4:

score: 0
Accepted
time: 1ms
memory: 5976kb

Test #5:

score: 0
Accepted
time: 1ms
memory: 5908kb

Test #6:

score: 0
Accepted
time: 4ms
memory: 5912kb

Test #7:

score: 0
Accepted
time: 0ms
memory: 8008kb

Test #8:

score: 0
Accepted
time: 2ms
memory: 4420kb

Test #9:

score: 0
Accepted
time: 368ms
memory: 34644kb

Test #10:

score: 0
Accepted
time: 247ms
memory: 23676kb

Test #11:

score: 0
Accepted
time: 484ms
memory: 51492kb

Test #12:

score: 0
Accepted
time: 1ms
memory: 4052kb

Test #13:

score: 0
Accepted
time: 0ms
memory: 6100kb

Test #14:

score: 0
Accepted
time: 0ms
memory: 4188kb

Test #15:

score: 0
Accepted
time: 2ms
memory: 4328kb

Test #16:

score: 0
Accepted
time: 4ms
memory: 8156kb

Test #17:

score: 0
Accepted
time: 10ms
memory: 6620kb

Test #18:

score: 0
Accepted
time: 53ms
memory: 8120kb

Test #19:

score: 0
Accepted
time: 323ms
memory: 18216kb

Test #20:

score: 0
Accepted
time: 1961ms
memory: 55000kb

Test #21:

score: 0
Accepted
time: 55ms
memory: 26716kb

Test #22:

score: 0
Accepted
time: 61ms
memory: 26372kb

Test #23:

score: 0
Accepted
time: 69ms
memory: 30296kb

Test #24:

score: 0
Accepted
time: 45ms
memory: 21576kb

Test #25:

score: 0
Accepted
time: 50ms
memory: 22884kb

Test #26:

score: 0
Accepted
time: 88ms
memory: 29852kb

Test #27:

score: 0
Accepted
time: 1678ms
memory: 59236kb

Test #28:

score: 0
Accepted
time: 660ms
memory: 42356kb

Test #29:

score: 0
Accepted
time: 2216ms
memory: 77384kb

Test #30:

score: 0
Accepted
time: 3387ms
memory: 79852kb

Test #31:

score: 0
Accepted
time: 2901ms
memory: 78888kb

Test #32:

score: 0
Accepted
time: 3046ms
memory: 78796kb

Test #33:

score: 0
Accepted
time: 3158ms
memory: 78792kb

Test #34:

score: 0
Accepted
time: 3002ms
memory: 80272kb

Test #35:

score: 0
Accepted
time: 284ms
memory: 80208kb

Test #36:

score: 0
Accepted
time: 257ms
memory: 79028kb

Test #37:

score: 0
Accepted
time: 3551ms
memory: 78484kb

Test #38:

score: 0
Accepted
time: 842ms
memory: 103168kb

Test #39:

score: 0
Accepted
time: 315ms
memory: 95248kb

Test #40:

score: 0
Accepted
time: 818ms
memory: 75780kb

Test #41:

score: 0
Accepted
time: 331ms
memory: 81452kb

Test #42:

score: 0
Accepted
time: 340ms
memory: 81996kb

Test #43:

score: 0
Accepted
time: 336ms
memory: 84048kb

Test #44:

score: 0
Accepted
time: 371ms
memory: 89376kb

Test #45:

score: 0
Accepted
time: 369ms
memory: 87856kb

Test #46:

score: 0
Accepted
time: 1ms
memory: 5968kb

Test #47:

score: 0
Accepted
time: 199ms
memory: 53020kb

Test #48:

score: 0
Accepted
time: 1ms
memory: 5988kb

Test #49:

score: 0
Accepted
time: 2093ms
memory: 78132kb

Test #50:

score: 0
Accepted
time: 60ms
memory: 29924kb

Test #51:

score: 0
Accepted
time: 1ms
memory: 3872kb

Test #52:

score: 0
Accepted
time: 1ms
memory: 3872kb

Test #53:

score: 0
Accepted
time: 1ms
memory: 6092kb

Test #54:

score: 0
Accepted
time: 1ms
memory: 3948kb

Test #55:

score: 0
Accepted
time: 1ms
memory: 5976kb

Test #56:

score: 0
Accepted
time: 1ms
memory: 5964kb

Test #57:

score: 0
Accepted
time: 0ms
memory: 6016kb

Test #58:

score: 0
Accepted
time: 8ms
memory: 8984kb

Test #59:

score: 0
Accepted
time: 260ms
memory: 23092kb

Test #60:

score: 0
Accepted
time: 792ms
memory: 45144kb

Test #61:

score: 0
Accepted
time: 2073ms
memory: 69076kb

Test #62:

score: 0
Accepted
time: 2195ms
memory: 77616kb

Test #63:

score: 0
Accepted
time: 227ms
memory: 76136kb

Test #64:

score: 0
Accepted
time: 237ms
memory: 75040kb

Test #65:

score: 0
Accepted
time: 233ms
memory: 76176kb

Test #66:

score: 0
Accepted
time: 812ms
memory: 75488kb

Test #67:

score: 0
Accepted
time: 285ms
memory: 95288kb

Test #68:

score: 0
Accepted
time: 699ms
memory: 101960kb

Test #69:

score: 0
Accepted
time: 325ms
memory: 104304kb

Test #70:

score: 0
Accepted
time: 346ms
memory: 104672kb