oj.uz

Submission #113903

# Submission time Handle Problem Language Result Execution time Memory
113903 2019-05-29T07:24:11 Z Mahdi_Jfri Chase (CEOI17_chase) C++14
100 / 100
 856 ms 390496 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[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[i][0] = dpu[v][i][0] , mx[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[i - 1][0] + sum[u]);
						dpu[u][i][1] = max(dpu[u][i][1] , mx[i - 1][1] + sum[u] - x[u]);
					}

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

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

					mx[i][0] = max(mx[i][0] , dpd[u][i][0]);
					mx[i][0] = max(mx[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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 10 ms 6656 KB Output is correct
8 Correct 10 ms 6528 KB Output is correct
9 Correct 9 ms 6528 KB Output is correct
10 Correct 10 ms 6528 KB Output is correct
11 Correct 10 ms 6528 KB Output is correct
12 Correct 9 ms 6528 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 771 ms 390364 KB Output is correct
2 Correct 772 ms 390484 KB Output is correct
3 Correct 637 ms 385520 KB Output is correct
4 Correct 841 ms 385056 KB Output is correct
5 Correct 809 ms 385132 KB Output is correct
6 Correct 856 ms 384996 KB Output is correct
7 Correct 805 ms 385188 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 10 ms 6656 KB Output is correct
8 Correct 10 ms 6528 KB Output is correct
9 Correct 9 ms 6528 KB Output is correct
10 Correct 10 ms 6528 KB Output is correct
11 Correct 10 ms 6528 KB Output is correct
12 Correct 9 ms 6528 KB Output is correct
13 Correct 771 ms 390364 KB Output is correct
14 Correct 772 ms 390484 KB Output is correct
15 Correct 637 ms 385520 KB Output is correct
16 Correct 841 ms 385056 KB Output is correct
17 Correct 809 ms 385132 KB Output is correct
18 Correct 856 ms 384996 KB Output is correct
19 Correct 805 ms 385188 KB Output is correct
20 Correct 824 ms 384868 KB Output is correct
21 Correct 825 ms 385144 KB Output is correct
22 Correct 827 ms 385012 KB Output is correct
23 Correct 793 ms 385016 KB Output is correct
24 Correct 824 ms 385080 KB Output is correct
25 Correct 632 ms 385012 KB Output is correct
26 Correct 794 ms 390496 KB Output is correct
27 Correct 772 ms 390408 KB Output is correct