Submission #256336

#TimeUsernameProblemLanguageResultExecution timeMemory
256336uacoder123Biochips (IZhO12_biochips)C++14
100 / 100
498 ms405880 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define F first #define S second #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i) #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i) #define all(x) (x).begin(), (x).end() #define sz(x) int(x.size()) #define mp(i,a) make_pair(i,a) #define pb(a) push_back(a) #define bit(x,b) (x&(1LL<<b)) typedef long long int lli; typedef pair <lli,lli> ii; typedef pair <lli,ii> iii; typedef vector <lli> vi; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; int arr[200001][501]={}; int n,m; vi al[200001]; int val[200001]; int dp[501]={}; void dfs(int node,int p) { for(int i=1;i<=m;++i) { if(dp[i-1]==-1) { arr[node][i]=-1; continue; } arr[node][i]=dp[i-1]+val[node]; } for(int i=0;i<al[node].size();++i) if(al[node][i]!=p) dfs(al[node][i],node); for(int i=1;i<=m;++i) dp[i]=max(dp[i],arr[node][i]); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>m; int r; for(int i=1;i<=m;++i) dp[i]=-1; for(int i=1;i<=n;++i) { int f,w; cin>>f>>w; if(f!=0) { al[f].pb(i); al[i].pb(f); } else r=i; val[i]=w; } dfs(r,r); cout<<dp[m]<<endl; return(0); }

Compilation message (stderr)

biochips.cpp: In function 'void dfs(int, int)':
biochips.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~
biochips.cpp: In function 'int main()':
biochips.cpp:63:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   dfs(r,r);
   ~~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...