oj.uz

답안 #113902

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
113902 2019-05-29T07:20:48 Z Mahdi_Jfri Chase (CEOI17_chase) C++14
40 / 100
 876 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int maxn = 1e5 + 20;
const int maxv = 1e2 + 20;

int x[maxn];

vector<int> adj[maxn];

ll dpd[maxn][maxv][2] , mx[maxn][maxv][2] , dpu[maxn][maxv][2] , sum[maxn];

void dfs(int v , int p = -1)
{
	dpd[v][0][1] = -1e18;
	for(int i = 1; i < maxv; i++)
		dpd[v][i][1] = sum[v];

	for(auto u : adj[v])
		if(u != p)
		{
			dfs(u , v);

			for(int i = 0; i < maxv; i++)
			{
				if(i)
				{
					dpd[v][i][1] = max(dpd[v][i][1] , dpd[u][i - 1][0] + sum[v]);
					dpd[v][i][1] = max(dpd[v][i][1] , dpd[u][i - 1][1] + sum[v] - x[v]);
				}

				dpd[v][i][0] = max(dpd[v][i][0] , dpd[u][i][0]);
				dpd[v][i][0] = max(dpd[v][i][0] , dpd[u][i][1] - x[v]);
			}
		}
}

void sfd(int v , int p = -1)
{
	dpu[v][0][1] = -1e18;
	for(int i = 1; i < maxv; i++)
		dpu[v][i][1] = max(dpu[v][i][1] , sum[v]);

	for(int _ = 0; _ < 2; _++)
	{
		reverse(adj[v].begin() , adj[v].end());
		for(int i = 0; i < maxv; i++)
			mx[v][i][0] = dpu[v][i][0] , mx[v][i][1] = dpu[v][i][1];

		for(auto u : adj[v])
			if(u != p)
			{
				for(int i = 0; i < maxv; i++)
				{
					if(i)
					{
						dpu[u][i][1] = max(dpu[u][i][1] , mx[v][i - 1][0] + sum[u]);
						dpu[u][i][1] = max(dpu[u][i][1] , mx[v][i - 1][1] + sum[u] - x[u]);
					}

					dpu[u][i][0] = max(dpu[u][i][0] , mx[v][i][0]);
					dpu[u][i][0] = max(dpu[u][i][0] , mx[v][i][1] - x[u]);
				}

				for(int i = 0; i < maxv; i++)
				{
					if(i)
					{
						mx[v][i][1] = max(mx[v][i][1] , dpd[u][i - 1][0] + sum[v]);
						mx[v][i][1] = max(mx[v][i][1] , dpd[u][i - 1][1] + sum[v] - x[v]);
					}

					mx[v][i][0] = max(mx[v][i][0] , dpd[u][i][0]);
					mx[v][i][0] = max(mx[v][i][0] , dpd[u][i][1] - x[v]);
				}
			}
	}

	for(auto u : adj[v])
		if(u != p)
			sfd(u , v);
}

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

	int n , v;
	cin >> n >> v;

	for(int i = 0; i < n; i++)
		cin >> x[i];

	for(int i = 0; i < n - 1; i++)
	{
		int a , b;
		cin >> a >> b;
		a-- , b--;

		adj[a].pb(b);
		adj[b].pb(a);

		sum[a] += x[b] , sum[b] += x[a];
	}

	dfs(0);
	sfd(0);

	ll res = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < 2; j++)
			res = max(res , max(dpd[i][v][j] , dpu[i][v][j]));

	cout << res << endl;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 3 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 13 ms 8448 KB Output is correct
8 Correct 11 ms 8448 KB Output is correct
9 Correct 11 ms 8448 KB Output is correct
10 Correct 12 ms 8448 KB Output is correct
11 Correct 12 ms 8448 KB Output is correct
12 Correct 12 ms 8448 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 876 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 3 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 13 ms 8448 KB Output is correct
8 Correct 11 ms 8448 KB Output is correct
9 Correct 11 ms 8448 KB Output is correct
10 Correct 12 ms 8448 KB Output is correct
11 Correct 12 ms 8448 KB Output is correct
12 Correct 12 ms 8448 KB Output is correct
13 Runtime error 876 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -