oj.uz

답안 #127199

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
127199 2019-07-09T06:20:51 Z srvlt Fireworks (APIO16_fireworks) C++14
7 / 100
 12 ms 7672 KB 
#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];
}

Compilation message

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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 11 ms 7544 KB Output is correct
4 Correct 11 ms 7544 KB Output is correct
5 Correct 12 ms 7672 KB Output is correct
6 Correct 11 ms 7672 KB Output is correct
7 Correct 12 ms 7544 KB Output is correct
8 Correct 12 ms 7544 KB Output is correct
9 Correct 11 ms 7416 KB Output is correct
10 Correct 11 ms 7416 KB Output is correct

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 11 ms 7544 KB Output is correct
4 Correct 11 ms 7544 KB Output is correct
5 Correct 12 ms 7672 KB Output is correct
6 Correct 11 ms 7672 KB Output is correct
7 Correct 12 ms 7544 KB Output is correct
8 Correct 12 ms 7544 KB Output is correct
9 Correct 11 ms 7416 KB Output is correct
10 Correct 11 ms 7416 KB Output is correct
11 Incorrect 8 ms 7416 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 11 ms 7544 KB Output is correct
4 Correct 11 ms 7544 KB Output is correct
5 Correct 12 ms 7672 KB Output is correct
6 Correct 11 ms 7672 KB Output is correct
7 Correct 12 ms 7544 KB Output is correct
8 Correct 12 ms 7544 KB Output is correct
9 Correct 11 ms 7416 KB Output is correct
10 Correct 11 ms 7416 KB Output is correct
11 Incorrect 8 ms 7416 KB Output isn't correct
12 Halted 0 ms 0 KB -