oj.uz

Submission #126996

# Submission time Handle Problem Language Result Execution time Memory
126996 2019-07-08T18:37:24 Z srvlt Fireworks (APIO16_fireworks) C++14
7 / 100
 40 ms 35704 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 int long long
using namespace std;

const int N = 3e5 + 3;
int n, m, d[N], fv[N], sv[N];
vector <pair <int, int> > q[N];
multiset <int> f[N], s[N];

void add(int v, int x) {
    if (!s[v].empty() && *s[v].begin() > x) {
        f[v].insert(x);
        fv[v] += x;
    }   else {
        s[v].insert(x);
        sv[v] += x;
    }
    if (f[v].size() > s[v].size()) {
        int tmp = *(--f[v].end());
        f[v].erase(--f[v].end());
        fv[v] -= tmp;
        s[v].insert(tmp);
        sv[v] += tmp;
    }
    if (s[v].size() > f[v].size() + 1) {
        int tmp = *s[v].begin();
        s[v].erase(s[v].begin());
        sv[v] -= tmp;
        f[v].insert(tmp);
        fv[v] += tmp;
    }
}

int get(int v) {
    int x = *s[v].begin();
    return (x * (int)f[v].size() - fv[v]) + (sv[v] - x * (int)s[v].size());
}

void dfs(int v, int p) {
    for (auto i : q[v]) {
        if (i.fi != p) {
            dfs(i.fi, v);
            d[v] += d[i.fi];
            add(v, d[i.fi] + i.se);
        }
    }
    if (q[v].size() > 2)
        d[v] += get(v);
}

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<<d[1];
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 35556 KB Output is correct
2 Correct 37 ms 35576 KB Output is correct
3 Correct 33 ms 35580 KB Output is correct
4 Correct 34 ms 35576 KB Output is correct
5 Correct 40 ms 35576 KB Output is correct
6 Correct 33 ms 35704 KB Output is correct
7 Correct 34 ms 35576 KB Output is correct
8 Correct 34 ms 35704 KB Output is correct
9 Correct 36 ms 35636 KB Output is correct
10 Correct 34 ms 35704 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 35576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 35556 KB Output is correct
2 Correct 37 ms 35576 KB Output is correct
3 Correct 33 ms 35580 KB Output is correct
4 Correct 34 ms 35576 KB Output is correct
5 Correct 40 ms 35576 KB Output is correct
6 Correct 33 ms 35704 KB Output is correct
7 Correct 34 ms 35576 KB Output is correct
8 Correct 34 ms 35704 KB Output is correct
9 Correct 36 ms 35636 KB Output is correct
10 Correct 34 ms 35704 KB Output is correct
11 Incorrect 33 ms 35576 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 35556 KB Output is correct
2 Correct 37 ms 35576 KB Output is correct
3 Correct 33 ms 35580 KB Output is correct
4 Correct 34 ms 35576 KB Output is correct
5 Correct 40 ms 35576 KB Output is correct
6 Correct 33 ms 35704 KB Output is correct
7 Correct 34 ms 35576 KB Output is correct
8 Correct 34 ms 35704 KB Output is correct
9 Correct 36 ms 35636 KB Output is correct
10 Correct 34 ms 35704 KB Output is correct
11 Incorrect 33 ms 35576 KB Output isn't correct
12 Halted 0 ms 0 KB -