Submission #898753

#	Time	Username	Problem	Language	Result	Execution time	Memory
898753		vjudge1	Magic Tree (CEOI19_magictree)	C++17	6 / 100	1344 ms	84272 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
const int mxn=21;
int n,m,k,dp[mxn][1<<20],par[mxn],fru[mxn][mxn],sz;
vector<int>v[mxn];
void dfs(int z,int j){
	for(auto i:v[z]){
		if(!(j&(1<<i-1)))
			dfs(i,j);
	}
	sz++;
}
int main(){
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++){
		cin>>par[i];
		v[par[i]].push_back(i);
	}
	for(int i=1;i<=m;i++){
		int d,x,y;
		cin>>x>>d>>y;
		fru[x][d]=y;
	}
	for(int i=1;i<=k;i++){
		for(int j=1;j<(1<<n);j++){
			sz=0;
			dfs(1,j);
			if(sz==n-__builtin_popcount(j)){//cout<<j<<" ";
				dp[i][j]=dp[i-1][j];
				for(int w=1;w<=n;w++){
					if((j&(1<<w)) && !(j&(1<<par[w+1]-1))){
						dp[i][j]=max(dp[i][j],dp[i][j-(1<<w)]+fru[w+1][i]);
					}
				}
			}
			}
	}
	int ans=0;
	for(int j=1;j<(1<<n);j++){
		ans=max(ans,dp[k][j]);
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

magictree.cpp: In function 'void dfs(int, int)':
magictree.cpp:8:15: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    8 |   if(!(j&(1<<i-1)))
      |              ~^~
magictree.cpp: In function 'int main()':
magictree.cpp:31:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   31 |      if((j&(1<<w)) && !(j&(1<<par[w+1]-1))){
      |                               ~~~~~~~~^~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17