oj.uz

Submission #308490

# Submission time Handle Problem Language Result Execution time Memory
308490 2020-10-01T12:36:43 Z shivensinha4 Dostavljač (COCI18_dostavljac) C++17
0 / 140
 38 ms 2392 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXN = 501;
int n, t;
int ret[MXN+1][MXN+1], noret[MXN+1][MXN+1], val[MXN+1];
vi adj[MXN+1];

void dfs(int p, int parent) {
	ret[p][1] = noret[p][1] = val[p];
	int cret[t+1], cnoret[t+1];
	
	for (int i: adj[p]) if (i != parent) {
		dfs(i, p);
		
		for_(j, 0, t+1) {
			cret[j] = ret[p][j];
			cnoret[j] = noret[p][j];
		}
		for_(a, 0, t) {
			if (ret[p][a]) for_(b, 0, t-a) {
				if (ret[i][b] and a+b+2 <= t) cret[a+b+2] = max(cret[a+b+2], ret[p][a]+ret[i][b]);
				if (noret[i][b]) cnoret[a+b+1] = max(cnoret[a+b+1], ret[p][a]+noret[i][b]);
			}
			if (noret[p][a]) for_(b, 0, t-a-1) if (ret[b]) cnoret[a+b+1] = max(cnoret[a+b+1], noret[p][a]+ret[i][b]);
		}
		for_(j, 0, t+1) {
			ret[p][j] = cret[j];
			noret[p][j] = cnoret[j];
		}
	}
}


int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> t;
	for_(i, 0, n) cin >> val[i];
	for_(i, 0, n-1) {
		int a, b; cin >> a >> b;
		a -= 1; b -= 1;
		adj[a].push_back(b); adj[b].push_back(a); 
	}
	
	dfs(0, 0);
	
	int ans = 0;
	for_(i, 0, t+1) ans = max(ans, noret[0][i]);
	
	cout << ans << endl;

	return 0;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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