oj.uz

답안 #240137

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
240137 2020-06-18T07:28:19 Z MrRobot_28 Dostavljač (COCI18_dostavljac) C++17
14 / 140
 596 ms 4472 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 384 KB Output isn't correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 384 KB Output isn't correct

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 82 ms 1280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 88 ms 1536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 306 ms 2944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 596 ms 4472 KB Output isn't correct
2 Halted 0 ms 0 KB -