oj.uz

Submission #899244

# Submission time Handle Problem Language Result Execution time Memory
899244 2024-01-05T16:14:09 Z Denisov Fireworks (APIO16_fireworks) C++14
7 / 100
 6 ms 20828 KB 
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 3e5 + 11, inf = 1000111222;


vector <pii> edge[max_n];

int n, m;

ll ans = 0;

bool del[max_n];

inline bool dfs (int v, int p = -1, bool gg = false) {
    bool ok = v >= n || gg;
    bool there = v >= n;
    for (auto [to, len] : edge[v]) {
        if (to == p) {
            continue;
        }
        if (dfs(to, v, ok)) {
            there = true;
            if (ok) {
                ans += len;
            }
        }
    }
    if (v >= n && !gg) {
        del[v] = true;
    }
    return there;
}

bool need[max_n];

priority_queue <ll> q[max_n];
ll b[max_n];
int k[max_n];

inline void solve (int v, int p = -1) {
    for (auto [to, len] : edge[v]) {
        if (to == p) {
            continue;
        }
        if (del[to]) {
            need[v] = true;
            b[v] -= len;
            ++k[v];
            q[v].push(len);
            q[v].push(len);
        }
        else {
            solve(to, v);
            if (!need[to]) {
                continue;
            }
            need[v] = true;
            int to_del = k[to] - 1;
            ll s = 0;
            for (int i = 0; i < to_del; i++) {
                s += q[to].top();
                q[to].pop();
            }
            ll a2 = q[to].top() + len;
            q[to].pop();
            ll a1 = q[to].top() + len;
            q[v].push(a1);
            q[v].push(a2);
            b[v] += b[to] - len + s;
            ++k[v];
        }
    }
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1, p, c; i < n + m; i++) {
        cin >> p >> c;
        --p;
        edge[p].pb({i, c});
        edge[i].pb({p, c});
    }
    dfs(0);
    solve(0);
    while (k[0] > 0) {
        b[0] += q[0].top();
        q[0].pop();
        --k[0];
    }
    assert(!q[0].empty());
    cout << b[0] + ans << '\n';
}

Compilation message

fireworks.cpp: In function 'bool dfs(int, int, bool)':
fireworks.cpp:61:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for (auto [to, len] : edge[v]) {
      |               ^
fireworks.cpp: In function 'void solve(int, int)':
fireworks.cpp:85:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |     for (auto [to, len] : edge[v]) {
      |               ^

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20716 KB Output is correct
2 Correct 4 ms 20788 KB Output is correct
3 Incorrect 4 ms 20824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 4 ms 20824 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20828 KB Output is correct
5 Correct 5 ms 20828 KB Output is correct
6 Correct 5 ms 20828 KB Output is correct
7 Correct 6 ms 20792 KB Output is correct
8 Correct 4 ms 20828 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 6 ms 20716 KB Output is correct
12 Correct 4 ms 20788 KB Output is correct
13 Incorrect 4 ms 20824 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 4 ms 20824 KB Output is correct
3 Correct 4 ms 20828 KB Output is correct
4 Correct 4 ms 20828 KB Output is correct
5 Correct 5 ms 20828 KB Output is correct
6 Correct 5 ms 20828 KB Output is correct
7 Correct 6 ms 20792 KB Output is correct
8 Correct 4 ms 20828 KB Output is correct
9 Correct 4 ms 20828 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 6 ms 20716 KB Output is correct
12 Correct 4 ms 20788 KB Output is correct
13 Incorrect 4 ms 20824 KB Output isn't correct
14 Halted 0 ms 0 KB -