oj.uz

Submission #205904

# Submission time Handle Problem Language Result Execution time Memory
205904 2020-03-01T10:13:32 Z himyu Fireworks (APIO16_fireworks) C++17
26 / 100
 10 ms 7544 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

template <class T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

vector<pli> adj[300001];
const i64 inf = numeric_limits<i64>::max() / 3;

inline i64 ab(i64 x) { return x > 0 ? x : -x; }

class slope {
   public:
    vector<i64> bp;
    i64 sac, pen;

    slope() {
        bp.clear();
        sac = 0, pen = 0;
    }

    void push(i64 x) {
        if (bp.empty()) {
            bp.emplace_back(x);
            bp.emplace_back(x);
            ++sac;
            return;
        }

        while (bp.size() > sac + 1) bp.pop_back();
        bp[sac] += x;
        bp[sac - 1] += x;
    }

    i64 get(int x) {
        if(bp.empty()) return 0;

        i64 ret = 0;
        if (x > bp[sac])
            for (int i = sac; i < bp.size(); i++) ret += max(x - bp[i], 0LL);
        if (x < bp[sac - 1])
            for (int i = sac - 1; i >= 0; i--) ret += max(bp[i] - x, 0LL);
        return ret;
    }

    void print() {
        cout<<"sac: "<<sac<<endl;
        cout<<"pen: "<<pen<<endl;
        cout<<"bp: ";
        for(auto el:bp) cout<<el<<" ";
        cout<<endl;
    }
};

slope operator+(slope &lhs, slope &rhs) {
    slope ret;
    ret.sac = lhs.sac + rhs.sac;
    ret.pen = lhs.pen + rhs.pen;
    for (auto el : lhs.bp) ret.bp.emplace_back(el);
    for (auto el : rhs.bp) ret.bp.emplace_back(el);
    sort(iterall(ret.bp));
    ret.pen += lhs.get(ret.bp[ret.sac]);
    ret.pen += rhs.get(ret.bp[ret.sac]);

    return ret;
}

slope solve(int h, int p = -1) {
    auto mer = slope();

    for (auto [t, wf] : adj[h]) {
        if (t == p) continue;
        auto chslp = solve(t, h);
        chslp.push(wf);
        mer = mer + chslp;
    }

    return mer;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    for (int i = 2; i <= N + M; i++) {
        i64 j, w;
        cin >> j >> w;

        adj[i].emplace_back(j, w);
        adj[j].emplace_back(i, w);
    }

    cout << solve(1).pen << endl;

    return 0;
}

Compilation message

fireworks.cpp: In member function 'void slope::push(i64)':
fireworks.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (bp.size() > sac + 1) bp.pop_back();
                ~~~~~~~~~~^~~~~~~~~
fireworks.cpp: In member function 'i64 slope::get(int)':
fireworks.cpp:55:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = sac; i < bp.size(); i++) ret += max(x - bp[i], 0LL);
                               ~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 10 ms 7416 KB Output is correct
4 Correct 10 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 9 ms 7416 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 10 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 10 ms 7416 KB Output is correct
12 Correct 9 ms 7416 KB Output is correct
13 Correct 9 ms 7416 KB Output is correct
14 Correct 9 ms 7416 KB Output is correct
15 Correct 9 ms 7416 KB Output is correct
16 Correct 10 ms 7544 KB Output is correct
17 Correct 10 ms 7416 KB Output is correct
18 Correct 9 ms 7416 KB Output is correct
19 Correct 9 ms 7416 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 10 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 10 ms 7416 KB Output is correct
8 Correct 9 ms 7420 KB Output is correct
9 Correct 10 ms 7464 KB Output is correct
10 Correct 10 ms 7428 KB Output is correct
11 Correct 10 ms 7416 KB Output is correct
12 Correct 9 ms 7416 KB Output is correct
13 Correct 10 ms 7416 KB Output is correct
14 Correct 10 ms 7416 KB Output is correct
15 Correct 9 ms 7416 KB Output is correct
16 Correct 9 ms 7416 KB Output is correct
17 Correct 9 ms 7416 KB Output is correct
18 Correct 9 ms 7416 KB Output is correct
19 Correct 10 ms 7416 KB Output is correct
20 Correct 9 ms 7416 KB Output is correct
21 Correct 10 ms 7416 KB Output is correct
22 Correct 9 ms 7416 KB Output is correct
23 Correct 9 ms 7416 KB Output is correct
24 Correct 9 ms 7416 KB Output is correct
25 Correct 9 ms 7416 KB Output is correct
26 Correct 10 ms 7544 KB Output is correct
27 Correct 10 ms 7416 KB Output is correct
28 Correct 9 ms 7416 KB Output is correct
29 Correct 9 ms 7416 KB Output is correct
30 Incorrect 10 ms 7416 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 10 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 10 ms 7416 KB Output is correct
7 Correct 10 ms 7416 KB Output is correct
8 Correct 9 ms 7420 KB Output is correct
9 Correct 10 ms 7464 KB Output is correct
10 Correct 10 ms 7428 KB Output is correct
11 Correct 10 ms 7416 KB Output is correct
12 Correct 9 ms 7416 KB Output is correct
13 Correct 10 ms 7416 KB Output is correct
14 Correct 10 ms 7416 KB Output is correct
15 Correct 9 ms 7416 KB Output is correct
16 Correct 9 ms 7416 KB Output is correct
17 Correct 9 ms 7416 KB Output is correct
18 Correct 9 ms 7416 KB Output is correct
19 Correct 10 ms 7416 KB Output is correct
20 Correct 9 ms 7416 KB Output is correct
21 Correct 10 ms 7416 KB Output is correct
22 Correct 9 ms 7416 KB Output is correct
23 Correct 9 ms 7416 KB Output is correct
24 Correct 9 ms 7416 KB Output is correct
25 Correct 9 ms 7416 KB Output is correct
26 Correct 10 ms 7544 KB Output is correct
27 Correct 10 ms 7416 KB Output is correct
28 Correct 9 ms 7416 KB Output is correct
29 Correct 9 ms 7416 KB Output is correct
30 Incorrect 10 ms 7416 KB Output isn't correct
31 Halted 0 ms 0 KB -