Submission #7608392


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64

// n:10^4
int n;
vector<int> state[10101];
vector<int> in(10101, 0);
vector<int> c;
vector<int> ans;

void dfs(int s){
  vector<bool> visited(n, false);
  stack<int> st;
  st.push(s);
  int i = 0;

  while(!st.empty()){
    int fr=st.top(); st.pop();
    visited[fr] = true;
    ans[fr] = c[i++];
    for(int i=0;i<state[fr].size();++i){
      if (visited[state[fr][i]]) continue;
      st.push(state[fr][i]);
    }
  }
}

signed main() {
  cin>>n;
  for(int i=0;i<n-1;++i){
    int a,b;cin>>a>>b;--a;--b;
    state[a].emplace_back(b);
    state[b].emplace_back(a);
    ++in[a]; ++in[b];
  }

  c.resize(n);
  for(int i=0;i<n;++i) cin>>c[i];
  sort(c.begin(), c.end(), greater<int>());
  
  int root = 0;
  for(int i=0;i<n;++i){
    if(in[root] > in[i]){
      root = i;
    }
  }

  ans.resize(n);
  dfs(root);
  int m = accumulate(c.begin()+1, c.end(), 0);
  cout<<m<<endl;
  for(int i=0;i<n;++i){
    if (i>0) cout << " ";
    cout << ans[i];
  }
  cout << endl;
  return 0;
}

Submission Info

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

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
× 2
× 26
Set Name Test Cases
Sample example0.txt, example1.txt
All 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 896 KB
001.txt 12 ms 1152 KB
002.txt 7 ms 896 KB
003.txt 12 ms 1152 KB
004.txt 7 ms 896 KB
005.txt 12 ms 1152 KB
006.txt 7 ms 896 KB
007.txt 12 ms 1152 KB
008.txt 7 ms 896 KB
009.txt 12 ms 1152 KB
010.txt 7 ms 896 KB
011.txt 12 ms 1152 KB
012.txt 7 ms 896 KB
013.txt 12 ms 1152 KB
014.txt 7 ms 896 KB
015.txt 12 ms 1152 KB
016.txt 7 ms 896 KB
017.txt 12 ms 1152 KB
018.txt 7 ms 896 KB
019.txt 12 ms 1152 KB
020.txt 7 ms 768 KB
021.txt 12 ms 1024 KB
022.txt 6 ms 896 KB
023.txt 10 ms 1280 KB
example0.txt 1 ms 512 KB
example1.txt 1 ms 512 KB