oj.uz

Submission #128082

# Submission time Handle Problem Language Result Execution time Memory
128082 2019-07-10T11:59:28 Z srvlt Fireworks (APIO16_fireworks) C++14
7 / 100
 16 ms 7544 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 = 2e9;
int n, m, dp[N], k[N], tmp[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 g(int to, int x, int w1, int w0) {
    int t = x - w1;
    int d = t - k[to];
    d += M >> 1LL;
    int q1 = getsum(st1[to], 0, M, 0, d);
    int q2 = getsum(st1[to], 0, M, d + 1, M);
    int s1 = getsum(st2[to], 0, M, 0, d) - q1 * (M >> 1LL);
    int s2 = getsum(st2[to], 0, M, d + 1, M) - q2 * (M >> 1LL);
    d -= M >> 1LL;
    return dp[to] - tmp[to] + (q1 * d - s1 + s2 - q2 * d) + abs(w0 - w1);
}

int f(int v, int p, int x, bool ok = false) {
    int res = 0;
    for (auto i : q[v]) {
        int to = i.fi, w0 = i.se;
        if (to == p) {
            continue;
        }
        int w1 = 0, cost = 0;
        if (q[to].size() > 1) {
            int l = 0, r = x;
            while (l < r) {
                int mid = (l + r) >> 1LL;
                if (g(to, x, mid, w0) > g(to, x, mid + 1, w0)) {
                    l = mid + 1;
                }   else {
                    r = mid;
                }
            }
            w1 = l;
            cost = g(to, x, l, w0);
        }   else {
            w1 = x;
            cost = abs(w0 - w1);
        }
        res += cost;
        if (ok) {
            int d = w0 - w1;
            tmp[v] += abs(d);
            d += M >> 1LL;
            update(st1[v], 0, M, d, 1);
            update(st2[v], 0, M, d, d);
        }
    }
    return res;
}

void dfs(int v, int p) {
    st1[v] = new node(), st2[v] = new node();
    for (auto i : q[v]) {
        int to = i.fi, w0 = i.se;
        if (to == p) {
            continue;
        }
        dfs(to, v);
    }
    int l = 0, r = M >> 1LL;
    while (l < r) {
        int mid = (l + r) >> 1LL;
        if (f(v, p, mid) > f(v, p, mid + 1)) {
            l = mid + 1;
        }   else {
            r = mid;
        }
    }
    k[v] = l;
    dp[v] = f(v, p, l, true);
}

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:103:24: warning: unused variable 'w0' [-Wunused-variable]
         int to = i.fi, w0 = i.se;
                        ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct
4 Correct 8 ms 7544 KB Output is correct
5 Correct 8 ms 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 8 ms 7544 KB Output is correct
8 Correct 8 ms 7544 KB Output is correct
9 Correct 8 ms 7416 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Incorrect 16 ms 7416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct
4 Correct 8 ms 7544 KB Output is correct
5 Correct 8 ms 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 8 ms 7544 KB Output is correct
8 Correct 8 ms 7544 KB Output is correct
9 Correct 8 ms 7416 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 9 ms 7416 KB Output is correct
12 Incorrect 16 ms 7416 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7544 KB Output is correct
4 Correct 8 ms 7544 KB Output is correct
5 Correct 8 ms 7544 KB Output is correct
6 Correct 8 ms 7544 KB Output is correct
7 Correct 8 ms 7544 KB Output is correct
8 Correct 8 ms 7544 KB Output is correct
9 Correct 8 ms 7416 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 9 ms 7416 KB Output is correct
12 Incorrect 16 ms 7416 KB Output isn't correct
13 Halted 0 ms 0 KB -