Submission #1036990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036990		pera	Biochips (IZhO12_biochips)	C++17	10 / 100	51 ms	8476 KiB

biochips

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1 , LOG = 31;
int n , m , root = -1;
vector<int> mx(N);
vector<vector<int>> g(N);
void dfs(int u){
   for(int x = 0;x < (int)g[u].size();x ++){
      dfs(g[u][x]);
      mx[u] = max(mx[u] , mx[g[u][x]]);
   }
}
int main(){
   cin >> n >> m;
   for(int i = 1;i <= n;i ++){
      int p;
      cin >> p >> mx[i];
      if(p > 0){
         g[p].push_back(i);
      }else{
         root = i;
      }
   }
   dfs(root);
   vector<int> v;
   for(int x = 0;x < (int)g[root].size();x ++){
      v.push_back(mx[g[root][x]]);
   }
   sort(v.begin() , v.end());
   int s = 0;
   for(int x = 1;x <= m;x ++){
      s += v.back();
      v.pop_back();
   }
   if(m == 1){
      s = max(s , mx[root]);
   }
   cout << s << endl;
}

• Subtask 1: 10 / 100