Submission #1225631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225631		fermat	Biochips (IZhO12_biochips)	C++20	100 / 100	354 ms	403564 KiB

biochips

#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 2e5 + 5;

int n, m, x, y, root, a[N];

int dp[N][505], tin[N], tiktak, inf = 1e9 + 7, tout[N], ans, last;

vector < vector <int> > g;

vector < pair <int, int> > vec;

void dfs (int v)
{
 tin[v] = ++tiktak;
  
 for (auto to : g[v])
  dfs(to);
  
 tout[v] = tiktak;
 
 vec.pb( mk( tout[v], v ) );
}

main() 
{
 cin >> n >> m;
 g.resize(n + 1);
 
 for (int i = 1; i <= n; i++){
  scanf("%d%d", &x, &a[i]);
  if (x == 0)
   root = i;
  else
   g[x].pb(i);
 }
 dfs(root);
 
 sort( all(vec) );
 
 for (int i = 0; i <= n; i++)
  for (int j = 0; j <= m; j++)
   dp[i][j] = -inf;
   
 dp[0][0] = 0;
 
 for (auto it : vec)
 { 
  for (int l = last + 1; l <= it.fr; l++)
   for (int j = 0; j <= m; j++)
    dp[l][j] = max( dp[l][j], dp[l - 1][j] );
    
  for (int j = 1; j <= m; j++)
   dp[it.fr][j] = max( dp[ tin[it.sc] - 1 ][j - 1] + a[it.sc], dp[it.fr][j] );
   
    
  last = it.fr;
 }
 for (int j = 1; j <= n; j++)
  ans = max(dp[j][m], ans);
  
 cout << ans << endl;
}

Compilation message (stderr)

biochips.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main()
      | ^~~~
biochips.cpp: In function 'int main()':
biochips.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   scanf("%d%d", &x, &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100