제출 #127199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
127199		srvlt	Fireworks (APIO16_fireworks)	C++14	7 / 100	12 ms	7672 KiB

fireworks

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define val(x) (((x) == nullptr) ? 0 : ((x) -> s))
#define int long long
using namespace std;

const int N = 3e5 + 3, M = 1e9, inf = 1e18;
int n, m, dp[N], s[N];
vector <pair <int, int> > q[N];

struct node {
    node * l = nullptr, * r = nullptr;
    int s = 0;
};

node * st1[N], * st2[N];

void update(node * t, int tl, int tr, int x, int y) {
    if (tl == tr) {
        t -> s += y;
        return;
    }
    int tm = (tl + tr) >> 1LL;
    if (x <= tm) {
        if (t -> l == nullptr) {
            t -> l = new node();
        }
        update(t -> l, tl, tm, x, y);
    }   else {
        if (t -> r == nullptr) {
            t -> r = new node();
        }
        update(t -> r, tm + 1, tr, x, y);
    }
    t -> s = val(t -> l) + val(t -> r);
}

int getsum(node * t, int tl, int tr, int l, int r) {
    if (t == nullptr || tl > r || tr < l) {
        return 0;
    }
    if (tl >= l && tr <= r) {
        return t -> s;
    }
    int tm = (tl + tr) >> 1LL;
    return getsum(t -> l, tl, tm, l, r) + getsum(t -> r, tm + 1, tr, l, r);
}

int f(int v, int x) {
    int y = x * getsum(st1[v], 0, M, 0, x) - getsum(st2[v], 0, M, 0, x);
    int z = getsum(st2[v], 0, M, x + 1, M) - x * getsum(st1[v], 0, M, x + 1, M);
    return y + z;
}

pair <int, int> getans(int v, int to) {
    int l = -s[to], r = M - s[to], magic = 31;
    while (magic--) {
        int mid = (l + r) >> 1LL;
        if (f(v, s[to] + mid) > f(v, s[to] + mid + 1)) {
            l = mid;
        }   else {
            r = mid;
        }
    }
    return {f(v, s[to] + r), r};
}

void dfs(int v, int p) {
    st1[v] = new node(), st2[v] = new node();
    for (auto i : q[v]) {
        int to = i.fi, w = i.se;
        if (to != p) {
            dfs(to, v);
            dp[v] += dp[to];
            s[to] += w;
            update(st1[v], 0, M, s[to], 1);
            update(st2[v], 0, M, s[to], s[to]);
        }
    }
    int res = inf;
    for (auto i : q[v]) {
        int to = i.fi, w = i.se;
        if (to != p) {
            pair <int, int> tmp = getans(v, to);
            if (tmp.fi < res) {
                res = tmp.fi, s[v] = s[to] + tmp.se;
            }
        }
    }
    if (res == inf) {
        res = 0;
    }
    dp[v] += res;
//    cout<<"v: "<<v<<", dp["<<v<<"]: "<<dp[v]<<", s["<<v<<"]: "<<s[v]<<endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    for (int i = 2; i <= n + m; i++) {
        int x, y;
        cin>>x>>y;
        q[x].pb({i, y});
        q[i].pb({x, y});
    }
    dfs(1, 1);
    cout<<dp[1];
}

컴파일 시 표준 에러 (stderr) 메시지

fireworks.cpp: In function 'void dfs(long long int, long long int)':
fireworks.cpp:89:24: warning: unused variable 'w' [-Wunused-variable]
         int to = i.fi, w = i.se;
                        ^

• Subtask 1: 7 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45