Submission #277835

#TimeUsernameProblemLanguageResultExecution timeMemory
277835FashoMagic Tree (CEOI19_magictree)C++14
19 / 100
77 ms30456 KiB
#include <bits/stdc++.h> #define N 100005 #define ll long long int #define fo(i,x,y) for(int i=x;i<=y;i++) #define fs(ar,n) fo(i,1,n) cin>>ar[i] #define sp " " #define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false) #define pb push_back #define ppb pop_back #define fi first #define se second #define ii pair<int,int> #define lli pair<ll,ll> #define mod 1000000007 using namespace std; ll n,m,ar[N],sum,t,k,dp[1005][1005],val[N],dad[N],tut[N]; vector<int> v[N]; // vector<int> v2[N]; ll f(int ind,int back,int l) { if(dp[ind][l]!=-1) return dp[ind][l]; ll t1=0; ll t2=0; for(int i=0;i<v[ind].size();i++) t1+=f(v[ind][i],ind,l); if(ar[ind]<ar[l] && ar[ind]!=0) for(int i=0;i<v[ind].size();i++) t2+=f(v[ind][i],ind,ind); if(ar[ind]<ar[l] && ar[ind]!=0) t2+=val[ind]; if(ar[ind]==ar[l] && ar[l]!=0) t1+=val[ind]; // cout<<ind<<sp<<l<<sp<<t1<<sp<<t2<<endl; return dp[ind][l]=max(t1,t2); } // ll f(int ind,int back,int l) // { // if(dp[ind][l]!=-1) // return dp[ind][l]; // ll t1=0; // ll t2=0; // for(int i=0;i<v[ind].size();i++) // t1+=f(v[ind][i],ind,l); // if(ar[ind]<l && ar[ind]!=0) // for(int i=0;i<v[ind].size();i++) // t2+=f(v[ind][i],ind,ar[ind]); // if(ar[ind]<l && ar[ind]!=0) // t2+=val[ind]; // if(ar[ind]==l && l!=0) // t1+=val[ind]; // // cout<<ind<<sp<<l<<sp<<t1<<sp<<t2<<endl; // return dp[ind][l]=max(t1,t2); // } ll find(int x) { if(dad[x]==x) return x; return dad[x]=find(dad[x]); } int main() { fast; cin>>n>>m>>k; memset(dp,-1,sizeof(dp)); fo(i,2,n) { int a; cin>>a; // v[a].pb(i); dad[i]=a; } fo(i,1,m) { ll a,b,c; cin>>a>>b>>c; ar[a]=b; val[a]=c; } dad[1]=1; ar[0]=1e7; ll cnt=1; tut[1]=1; fo(i,2,n) if(ar[i]) { cnt++; v[tut[find(i)]].pb(cnt); tut[i]=cnt; ar[cnt]=ar[i]; val[cnt]=val[i]; // cout<<i<<sp<<tut[find(i)]<<endl; dad[i]=i; } cout<<f(1,1,0); // fo(i,1,n) // sum+=val[i]; // cout<<sum<<endl; // cout<<endl; // fo(i,1,n) // cout<<val[i]<<sp; // cout<<endl; }

Compilation message (stderr)

magictree.cpp: In function 'long long int f(int, int, int)':
magictree.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i=0;i<v[ind].size();i++)
      |              ~^~~~~~~~~~~~~~
magictree.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int i=0;i<v[ind].size();i++)
      |               ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...