oj.uz

Submission #716487

# Submission time Handle Problem Language Result Execution time Memory
716487 2023-03-30T07:26:23 Z vjudge1 Biochips (IZhO12_biochips) C++17
60 / 100
 2000 ms 388052 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 q[mx];
int a[mx];
int n,m,k;

void dfs(int v){
	for(int to:g[v])dfs(to);
	for(int to:g[v]){
		for(int i=m;i;i--){
			for(int j=i;j>=0;j--)dp[i][v]=max(dp[i][v],dp[i-j][v]+dp[j][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:48:6: note: 'r' was declared here
   48 |  int r;
      |      ^

Subtask #1
60.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 5156 KB Output is correct
4 Correct 17 ms 7600 KB Output is correct
5 Correct 27 ms 8624 KB Output is correct
6 Correct 54 ms 9644 KB Output is correct
7 Execution timed out 2068 ms 182604 KB Time limit exceeded
8 Execution timed out 2084 ms 182768 KB Time limit exceeded
9 Execution timed out 2086 ms 284544 KB Time limit exceeded
10 Execution timed out 2099 ms 388052 KB Time limit exceeded