oj.uz

Submission #106617

# Submission time Handle Problem Language Result Execution time Memory
106617 2019-04-19T09:23:03 Z lyc Fireworks (APIO16_fireworks) C++14
0 / 100
 10 ms 7424 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int N = 3e5+5;

int n, m;
vector<ii> al[N];

struct Slope {
    priority_queue<ll> points;
    ll a = 0, b = 0;
};

void print(priority_queue<ll> pq) { while (!pq.empty()) cout << pq.top() << endl, pq.pop(); }

Slope dfs(int u, int p) 
{
    Slope cur;
    if (SZ(al[u]) == 1 and al[u][0].fi == p) 
        cur.points.push(0), cur.points.push(0), cur.a = 1, cur.b = 0;
    else for (auto v : al[u]) if (v.fi != p) {
        Slope nxt = dfs(v.fi, u);
        ll x = nxt.points.top(); nxt.points.pop();
        ll y = nxt.points.top(); nxt.points.pop();
        nxt.points.push(x+v.sc);
        nxt.points.push(y+v.sc);
        nxt.b -= v.sc;

        if (SZ(nxt.points) > SZ(cur.points)) swap(nxt, cur);
        while (!nxt.points.empty()) {
            cur.points.push(nxt.points.top());
            nxt.points.pop();
        }
        cur.a += nxt.a; cur.b += nxt.b;
        
        while (cur.a > 1) {
            --cur.a;
            cur.b += cur.points.top();
            cur.points.pop();
        }
    }
    //cout << u << " :: " << cur.a << " " << cur.b << "\t\t\tSZ " << cur.points.size() << endl;
    //print(cur.points);
    return cur;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    FOR(i, 2, n+m){
        int p, c; cin >> p >> c;
        al[i].emplace_back(p, c);
        al[p].emplace_back(i, c);
    }

    Slope ans = dfs(1, 0);
    cout << ans.points.top()*ans.a + ans.b << '\n';
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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