Submission #5732751


Source Code Expand

Copy
#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

int main() {
  int N;
  cin >> N;
  vector< int > g[10000];
  for(int i = 1; i < N; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  vector< int > A(N);
  cin >> A;
  sort(begin(A), end(A));


  vector< int > deg(N);
  queue< int > que;
  for(int i = 0; i < N; i++) {
    deg[i] = g[i].size();
    if(deg[i] == 1) {
      que.emplace(i);
      --deg[i];
    }
  }
  vector< int > ans(N, N - 1);
  int ptr = 0;
  int64 ret = 0;
  while(que.size()) {
    auto p = que.front();
    que.pop();
    if(ptr + 1 < N) ret += A[ptr];
    ans[p] = ptr++;
    for(auto &t : g[p]) {
      --deg[t];
      if(deg[t] == 1) {
        que.emplace(t);
      }
    }
  }
  cout << ret << endl;
  for(int i = 0; i < N; i++) {
    cout << A[ans[i]] << " ";
  }
  cout << endl;
}






Submission Info

Submission Time
Task D - Maximum Sum of Minimum
User ei13333
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2622 Byte
Status
Exec Time 6 ms
Memory 1024 KB

Test Cases

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 4 ms 768 KB
001.txt 6 ms 1024 KB
002.txt 4 ms 768 KB
003.txt 6 ms 1024 KB
004.txt 4 ms 768 KB
005.txt 6 ms 1024 KB
006.txt 4 ms 768 KB
007.txt 6 ms 1024 KB
008.txt 4 ms 768 KB
009.txt 6 ms 1024 KB
010.txt 4 ms 768 KB
011.txt 6 ms 1024 KB
012.txt 4 ms 768 KB
013.txt 6 ms 1024 KB
014.txt 4 ms 768 KB
015.txt 6 ms 1024 KB
016.txt 4 ms 768 KB
017.txt 6 ms 1024 KB
018.txt 4 ms 768 KB
019.txt 6 ms 1024 KB
020.txt 4 ms 768 KB
021.txt 6 ms 1024 KB
022.txt 3 ms 768 KB
023.txt 6 ms 1024 KB
example0.txt 1 ms 512 KB
example1.txt 1 ms 512 KB