Submission #5737913


Source Code Expand

Copy
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
#define dump(x) cerr << #x " = " << x << endl
using ll = long long;
using namespace std;
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
template <class T, class U> inline void chmax(T & a, U const & b) { a = max<T>(a, b); }
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }
template <typename X, typename T> auto make_vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto make_vectors(X x, Y y, Z z, Zs... zs) { auto cont = make_vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
template <typename T> ostream & operator << (ostream & out, vector<T> const & xs) { REP (i, (int)xs.size() - 1) out << xs[i] << ' '; if (not xs.empty()) out << xs.back(); return out; }

ll get_score(int n, const vector<vector<int> > & g, const vector<ll> & c) {
    ll score = 0;
    REP (i, n) {
        for (int j : g[i]) if (i < j) {
            score += min(c[i], c[j]);
        }
    }
    return score;
}

pair<ll, vector<ll> > solve(int n, const vector<vector<int> > & g, vector<ll> c) {
    sort(ALL(c));
    reverse(ALL(c));
    auto it = c.begin();
    vector<ll> d(n, -1);

    function<void (int, int)> go = [&](int i, int parent) {
        d[i] = *(it ++);
        for (int j : g[i]) if (j != parent) {
            go(j, i);
        }
    };

    go(0, -1);
    return make_pair(get_score(n, g, d), d);
}

int main() {
    int n; cin >> n;
    vector<vector<int> > g(n);
    REP (i, n - 1) {
        int a, b; cin >> a >> b;
        -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<ll> c(n);
    REP (i, n) {
        cin >> c[i];
    }
    auto ans = solve(n, g, c);
    cout << ans.first << endl;
    cout << ans.second << endl;
    return 0;
}

Submission Info

Submission Time
Task D - Maximum Sum of Minimum
User kimiyuki
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2149 Byte
Status
Exec Time 12 ms
Memory 1792 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt, example1.txt
All 500 / 500 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt 7 ms 768 KB
001.txt 12 ms 1152 KB
002.txt 7 ms 768 KB
003.txt 12 ms 1152 KB
004.txt 7 ms 640 KB
005.txt 12 ms 1152 KB
006.txt 7 ms 640 KB
007.txt 12 ms 1152 KB
008.txt 7 ms 768 KB
009.txt 12 ms 1152 KB
010.txt 7 ms 640 KB
011.txt 12 ms 1152 KB
012.txt 7 ms 640 KB
013.txt 12 ms 1152 KB
014.txt 7 ms 768 KB
015.txt 12 ms 1152 KB
016.txt 7 ms 640 KB
017.txt 12 ms 1152 KB
018.txt 7 ms 640 KB
019.txt 12 ms 1152 KB
020.txt 7 ms 1024 KB
021.txt 12 ms 1792 KB
022.txt 6 ms 768 KB
023.txt 10 ms 1152 KB
example0.txt 1 ms 256 KB
example1.txt 1 ms 256 KB