oj.uz

답안 #784471

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
784471 2023-07-16T07:10:16 Z blue Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 173372 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
#define sz(x) int(x.size())

const int mx = 100'000;
const int mxv = 100;

int n;
int m;

vll w(1+mx, 0);

vi edge[1+mx];

vi par(1 + mx, 0);

vll wsum(1+mx, 0);

void dfs(int u)
{
	for(int v : edge[u])
	{
		if(par[u] == v)
			continue;

		par[v] = u;
		dfs(v);
	}
}




ll up[1+mx][1+mxv];
ll dn[1+mx][1+mxv];

ll res = 0;

void dfs2(int u)
{
	for(int v : edge[u])
	{
		if(par[u] != v)
			dfs2(v);
	}




	//1. calculate up

	up[u][0] = 0;
	for(int k = 1; k <= m; k++)
		up[u][k] = wsum[u];

	for(int k = 0; k <= m; k++)
	{
		for(int v : edge[u])
		{
			if(par[u] == v)
				continue;

			up[u][k] = max(up[u][k], up[v][k]);
			if(k > 0)
				up[u][k] = max(up[u][k], up[v][k-1] + wsum[u] - w[v]);
		}
	}





	//2. calculate down

	dn[u][0] = 0;
	for(int k = 1; k <= m; k++)
		dn[u][k] = wsum[u] - w[par[u]];

	for(int k = 0; k <= m; k++)
	{
		for(int v : edge[u])
		{
			if(par[u] == v)
				continue;

			dn[u][k] = max(dn[u][k], dn[v][k]);

			if(k > 0)
				dn[u][k] = max(dn[u][k], dn[v][k-1] + wsum[u] - w[par[u]]);
		}
	}



	//3. update res

	//single element
	if(m >= 1)
		res = max(res, wsum[u]);

	//up path
	res = max(res, up[u][m]);

	//down path
	for(int v : edge[u])
	{
		if(par[u] != v)
		{
			res = max(res, dn[v][m]);
			if(m-1 >= 0)
				res = max(res, dn[v][m-1] + wsum[u]);
		}
	}

	//combination
	vll temp(1+m, -1'000'000'000'000'000'000LL);
	for(int v : edge[u])
	{
		if(par[u] == v)
			continue;

		for(int j = 0; j <= m; j++)
			res = max(res, temp[m-j] + dn[v][j]);

		////////
		for(int j = 0; j <= m; j++)
		{
			temp[j] = max(temp[j], up[v][j]);
			if(j >= 1)
				temp[j] = max(temp[j], up[v][j-1] + wsum[u] - w[v]);
		}
	}
}





int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	
	for(int i = 1; i <= n; i++)
		cin >> w[i];

	for(int e = 1; e <= n-1; e++)
	{
		int a, b;
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	for(int i = 1; i <= n; i++)
		for(int j : edge[i])
			wsum[i] += w[j];

	for(int r = 1; r <= n; r++)
	{
		par = vi(1+n, 0);

		dfs(r);

		for(int i = 1; i <= n; i++)
		{
			for(int j = 0; j <= m; j++)
			{
				up[i][j] = 0;
				dn[i][j] = 0;
			}
		}

		dfs2(r);
	}

	

	cout << res << '\n';

}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Correct 2 ms 4564 KB Output is correct
3 Correct 2 ms 4564 KB Output is correct
4 Correct 2 ms 4564 KB Output is correct
5 Correct 3 ms 4640 KB Output is correct
6 Correct 3 ms 4564 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Correct 2 ms 4564 KB Output is correct
3 Correct 2 ms 4564 KB Output is correct
4 Correct 2 ms 4564 KB Output is correct
5 Correct 3 ms 4640 KB Output is correct
6 Correct 3 ms 4564 KB Output is correct
7 Correct 1343 ms 6028 KB Output is correct
8 Correct 138 ms 5964 KB Output is correct
9 Correct 105 ms 5812 KB Output is correct
10 Correct 1304 ms 5836 KB Output is correct
11 Correct 460 ms 5808 KB Output is correct
12 Correct 184 ms 5820 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4080 ms 173372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Correct 2 ms 4564 KB Output is correct
3 Correct 2 ms 4564 KB Output is correct
4 Correct 2 ms 4564 KB Output is correct
5 Correct 3 ms 4640 KB Output is correct
6 Correct 3 ms 4564 KB Output is correct
7 Correct 1343 ms 6028 KB Output is correct
8 Correct 138 ms 5964 KB Output is correct
9 Correct 105 ms 5812 KB Output is correct
10 Correct 1304 ms 5836 KB Output is correct
11 Correct 460 ms 5808 KB Output is correct
12 Correct 184 ms 5820 KB Output is correct
13 Execution timed out 4080 ms 173372 KB Time limit exceeded
14 Halted 0 ms 0 KB -