Submission #49240

#	Time	Username	Problem	Language	Result	Execution time	Memory
49240		IvanC	Dostavljač (COCI18_dostavljac)	C++17	0 / 140	383 ms	2892 KiB

dostavljac

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 510;

vector<int> grafo[MAXN];
int dp[MAXN][MAXN],tab[MAXN][MAXN],A[MAXN],e1[MAXN],e2[MAXN],nivel[MAXN],N,M,temporaria[MAXN];

void solve_1(int v,int p){
	for(int i = 1;i<=M;i++) dp[v][i] = A[v];
	for(int i = 0;i<grafo[v].size();i++){
		int idx = grafo[v][i];
		int u = (e1[idx] != v) ? (e1[idx]) : (e2[idx]);
		if(u == p) continue;
		nivel[u] = nivel[v] + 1;
		solve_1(u,v);
		for(int pega = 0;pega+2<=M;pega++){
			int peso = pega + 2;
			int vale = dp[u][pega];
			for(int j = M;j>=peso;j--){
				dp[v][j] = max(dp[v][j],dp[v][j - peso] + vale);
			}
		}
	}
	for(int i = 1;i<=M;i++) dp[v][i] = max(dp[v][i],dp[v][i-1]);
}

void solve_2(int v,int p){
	for(int i = 0;i<grafo[v].size();i++){
		int idx = grafo[v][i];
		int u = (e1[idx] != v) ? (e1[idx]) : (e2[idx]);
		if(u == p) continue;
		solve_2(u,v);
		for(int j = 0;j<=M;j++) temporaria[j] = 0;
		for(int j = 0;j<grafo[v].size();j++){
			int idx_linha = grafo[v][j];
			int w = (e1[idx_linha] != v) ? (e1[idx_linha]) : (e2[idx_linha]);
			if(u == p || i == j) continue;
			for(int pega = 0;pega+2<=M;pega++){
				int peso = pega + 2;
				int vale = dp[w][pega];
				for(int k = M;k>=peso;k--){
					temporaria[k] = max(temporaria[k],temporaria[k - peso] + vale);
				}
			}
		}
		for(int pega = 0;pega+1<=M;pega++){
			int peso = pega + 1;
			int vale = tab[u][pega];
			for(int j = M;j>=peso;j--){
				temporaria[j] = max(temporaria[j],temporaria[j - peso] + vale);
			}
		}
		for(int j = 0;j<=M;j++) tab[v][j] = max(tab[v][j],temporaria[j]);
	}
	for(int i = M;i>=1;i--) tab[v][i] = max(tab[v][i],tab[v][i-1] + A[v]);
	for(int i = 1;i<=M;i++) tab[v][i] = max(tab[v][i],tab[v][i-1]);
}

int main(){
	scanf("%d %d",&N,&M);
	for(int i = 1;i<=N;i++) scanf("%d",&A[i]);
	for(int i = 1;i<N;i++){
		scanf("%d %d",&e1[i],&e2[i]);
		grafo[e1[i]].push_back(i);
		grafo[e2[i]].push_back(i);
	}
	solve_1(1,-1);
	solve_2(1,-1);
	printf("%d\n",tab[1][M]);
	return 0;
}

Compilation message (stderr)

dostavljac.cpp: In function 'void solve_1(int, int)':
dostavljac.cpp:11:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<grafo[v].size();i++){
                ~^~~~~~~~~~~~~~~~
dostavljac.cpp: In function 'void solve_2(int, int)':
dostavljac.cpp:29:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<grafo[v].size();i++){
                ~^~~~~~~~~~~~~~~~
dostavljac.cpp:35:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0;j<grafo[v].size();j++){
                 ~^~~~~~~~~~~~~~~~
dostavljac.cpp: In function 'int main()':
dostavljac.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
  ~~~~~^~~~~~~~~~~~~~~
dostavljac.cpp:62:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1;i<=N;i++) scanf("%d",&A[i]);
                          ~~~~~^~~~~~~~~~~~
dostavljac.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&e1[i],&e2[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14