oj.uz

Submission #716559

# Submission time Handle Problem Language Result Execution time Memory
716559 2023-03-30T10:32:02 Z vjudge1 Biochips (IZhO12_biochips) C++17
100 / 100
 767 ms 387360 KB 
 #include <bits/stdc++.h>
#define f first
#define s second 
#define ent '\n'
//#define int long long

#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

//typedef long double ld;
typedef long long ll;
using namespace std;
 
struct node{double x,y;};
//double len(node a,node b)
//{return sqrt((a.x-b.x)*(a.x-b.y)+(a.y-b.y)*(a.x-b.y));}

struct seg{
	int mx1=0,mx2=0,ans=0;
};

const string out[2]={"NO\n","YES\n"};
const ll dx[]={0,0,1,-1,-1,1,1,-1};  
const ll dy[]={1,-1,0,0,-1,1,-1,1};
const int md=998244353;
const int mod=1e9+7;
const int mx=2e5+12; 
const int tst=1e5;
const bool T=0;

vector<int> g[mx];
int dp[501][mx];
int sz[mx];
int q[mx];
int a[mx];
int n,m,k;

void dfs(int v){
	for(int to:g[v])dfs(to);
	sz[v]=1;
	for(int to:g[v]){
		for(int i=min(m,sz[v]+sz[to]);i;i--){
			for(int j=min(sz[to],i);j>=0;j--)dp[i][v]=max(dp[i][v],dp[i-j][v]+dp[j][to]);
		}
		sz[v]+=sz[to];
	}
	dp[1][v]=max(dp[1][v],q[v]);
}

void Press_Fn_with_F11(){
	int r;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int p;
		cin>>p>>q[i];
		if(!p)r=i;
		for(int j=1;j<=m;j++)dp[j][i]=-1e9;
		g[p].push_back(i);
	}
	dfs(r);
	cout<<dp[m][r]<<ent;
}

signed main(){	
    ios_base::sync_with_stdio(0);
    cin.tie(0);		
    cout.tie(0);
    int Ersayin_abi_crush=1;
    if(T)cin>>Ersayin_abi_crush;
    for(int i=1;i<=Ersayin_abi_crush;i++){
//    	cout<<"Case "<<i<<": ";
    	Press_Fn_with_F11();
	}
}

Compilation message

biochips.cpp: In function 'void Press_Fn_with_F11()':
biochips.cpp:4:13: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
    4 | #define ent '\n'
      |             ^~~~
biochips.cpp:51:6: note: 'r' was declared here
   51 |  int r;
      |      ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 7 ms 7552 KB Output is correct
5 Correct 12 ms 8532 KB Output is correct
6 Correct 9 ms 9556 KB Output is correct
7 Correct 251 ms 181860 KB Output is correct
8 Correct 258 ms 181812 KB Output is correct
9 Correct 563 ms 283924 KB Output is correct
10 Correct 767 ms 387360 KB Output is correct