Submission #240137

#	Time	Username	Problem	Language	Result	Execution time	Memory
240137		MrRobot_28	Dostavljač (COCI18_dostavljac)	C++17	14 / 140	596 ms	4472 KiB

dostavljac

#include <bits/stdc++.h>
                  
using namespace std;
#define int long long
vector <vector <int> > g;
vector <int> a;
vector <int> h;
vector <vector <int> > pred;
vector <int> tin, tout;
bool pr(int a, int b)
{
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int len(int a, int b)
{
	if(pr(a, b))
	{
		return h[b] - h[a];
	}
	else if(pr(b, a))
	{
		return h[a] - h[b];
	}
	else
	{
		int sum = h[a] + h[b];
		for(int j = pred.size() - 1; j >= 0; j--)
		{
			if(!pr(pred[j][a], b))
			{
				a = pred[j][a];
			}
		}
		a = pred[0][a];
		return sum - 2 * h[a];
	}
}
int timer = 0;
vector <int> eiler;
void dfs(int v, int p = -1)
{
	tin[v] = timer++;
	eiler.push_back(v);
	for(int i = 0; i< g[v].size(); i++)
	{
		int to = g[v][i];
		if(to != p)
		{
			h[to] = h[v] + 1;
			pred[0][to] = v;
			dfs(to, v);
		}
	}
	tout[v] = timer++;
}
signed main(){
//	ios_base::sync_with_stdio(false);
//	cin.tie(NULL);
//	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	a.resize(n);
	g.resize(n);
	h.resize(n);
	tin.resize(n);
	tout.resize(n);
	int t = log2(n) + 1;
	pred.resize(t, vector <int> (n));
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for(int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(0);
	for(int i = 1; i < t; i++){
		for(int j = 0; j < n; j++)
		{
			pred[i][j] = pred[i - 1][pred[i - 1][j]];
		}
	}
	vector <vector <int> > dist(n, vector <int> (n));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++)
		{
			dist[i][j] = len(i, j);
		}
	}
	vector <vector <int> > dp(n, vector <int> (m + 1, -1e10));
	dp[0][0] = 0;
	dp[0][1] = a[0];
	int ans = 0;
	ans = a[0];
	for(int i = 1; i < n; i++)
	{
		for(int j = 0; j < i; j++)
		{
			int d = dist[eiler[i]][eiler[j]];
			for(int t = 0; t + d <= m; t++)
			{
				if(t + d  + 1 <= m)
				{
					dp[i][t + d + 1] = max(dp[i][t + d  + 1], dp[j][t] + a[eiler[i]]);
				}
				dp[i][t + d] = max(dp[i][t + d], dp[j][t]);
			}
			d = d + h[eiler[i]] - h[eiler[j]];
			for(int t = 0; t + d <= m; t++)
			{
				if(t + d >= 0)
				{
					dp[i][t + d] = max(dp[i][t + d], dp[j][t]);
				}
				if(t + d + 1 <= m && t +  d+ 1 >= 0)
				{
					dp[i][t + d + 1] = max(dp[i][t +  d + 1], dp[j][t] + a[eiler[i]]);
				}
			}
		}
		for(int t = 0; t <= m; t++)
		{
			ans = max(ans, dp[i][t]);
		}
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

dostavljac.cpp: In function 'void dfs(long long int, long long int)':
dostavljac.cpp:44:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i< g[v].size(); i++)
                 ~^~~~~~~~~~~~~

• Subtask 1: 14 / 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