oj.uz

Submission #49240

# Submission time Handle Problem Language Result Execution time Memory
49240 2018-05-24T01:05:49 Z IvanC Dostavljač (COCI18_dostavljac) C++17
0 / 140
 383 ms 2892 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 632 KB Output isn't correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 632 KB Output isn't correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 956 KB Output isn't correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 956 KB Output isn't correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 1516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 1888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 2460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 383 ms 2892 KB Output isn't correct
2 Halted 0 ms 0 KB -