Submission #164677

#	Time	Username	Problem	Language	Result	Execution time	Memory
164677		the_art_of_war	Fireworks (APIO16_fireworks)	C++14	100 / 100	343 ms	44136 KiB

fireworks

//
// Created by Ильдар Ялалов on 28.10.2019.
//
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 1e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
#define pb push_back
#define eb emplace_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define mp make_pair
#define all(a) a.begin(),a.end()
bool debug = 0;
const int MAXN = 3e5 + 100;
const int LOG = 21;
const int mod = 998244353;
const int MX = (1e7 + 100) * 1.5;
typedef long long li;

template<class T1, class T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &rhs) {
    out << "( " << rhs.first << " , " << rhs.second << " )";
    return out;
}

template<typename A, typename B>
string to_string(pair<A, B> p);

template<typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template<typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string &s) {
    return '"' + s + '"';
}

string to_string(const char *s) {
    return to_string((string) s);
}

string to_string(bool b) {
    return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for (int i = 0; i < static_cast<int>(v.size()); i++) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}

template<size_t N>
string to_string(bitset<N> v) {
    string res = "";
    for (size_t i = 0; i < N; i++) {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}

template<typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

template<typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template<typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template<typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " +
           to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef zxc
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif


int p[MAXN], c[MAXN];

ll a[MAXN], b[MAXN];
priority_queue<ll> q[MAXN];

void union_set(int i, int j) {
    a[i] += a[j];
    b[i] += b[j];
    if (q[i].size() < q[j].size())
        q[i].swap(q[j]);
    while (!q[j].empty()) {
        q[i].push(q[j].top());
        q[j].pop();
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 2; i <= n + m; ++i) {
        cin >> p[i] >> c[i];
    }

    for (int i = n + m; i >= 2; --i) {
        if (i > n) {
            a[i] = 1;
            b[i] = -c[i];
            q[i].push(c[i]);
            q[i].push(c[i]);
        } else {
            while (a[i] > 1) {
                a[i]--;
                b[i] += q[i].top();
                q[i].pop();
            }
            ll x = q[i].top();
            q[i].pop();
            ll y = q[i].top();
            q[i].pop();

            q[i].push(x + c[i]);
            q[i].push(y + c[i]);
            b[i] -= c[i];
        }
        union_set(p[i], i);
    }

    while(a[1] > 0){
        a[1]--;
        b[1]+=q[1].top();
        q[1].pop();
    }
    cout << b[1];
}


signed main() {
#ifdef zxc
    debug = 0;
    freopen("../input.txt", "r", stdin);
    //  freopen("../output.txt", "w", stdout);
#else

#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(20);

    int t = 1;
    while (t--)
        solve();
    if (debug)
        cerr << endl << "time : " << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
}

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