oj.uz

Submission #392010

# Submission time Handle Problem Language Result Execution time Memory
392010 2021-04-20T09:56:14 Z sinamhdv Chase (CEOI17_chase) C++11
40 / 100
 4000 ms 283112 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 100100
#define MAXB 110

int n, B;
int p[MAXN];
ll a[MAXN];
vector<int> adj[MAXN];
int efrom[MAXN], eto[MAXN];
bool mark[MAXN];
ll ans = 0;
int subtree[MAXN];
ll up[2 * MAXN][MAXB];
ll dn[MAXN][MAXB];
int cen, rt;
vector<int> dfs_ord[MAXN];
ll mxdn[MAXB], mxup[MAXB];
int _epar[MAXN];

void dfs1(int v, int par)
{
	subtree[v] = 1;
	for (int e : adj[v])
	{
		int u = efrom[e] ^ eto[e] ^ v;
		if (u == par || mark[u]) continue;
		dfs1(u, v);
		subtree[v] += subtree[u];
	}
}

int findcen(int v, int par, int sz)
{
	for (int e : adj[v])
	{
		int u = efrom[e] ^ eto[e] ^ v;
		if (u == par || mark[u]) continue;
		if (subtree[u] > sz/2) return findcen(u, v, sz);
	}
	return v;
}

void dfs2(int v, int par, int epar)
{
	dfs_ord[rt].pb(v);
	_epar[v] = epar;

	// calc up & dn
	FOR(k, 1, B + 1)
	{
		dn[v][k] = max(dn[par][k], dn[par][k - 1] + a[v] - p[par]);
		for (int e : adj[v])
		{
			int u = efrom[e] ^ eto[e] ^ v;
			if (mark[u] || u == par) continue;
			up[e][k] = max(up[epar][k], up[epar][k - 1] + a[v] - p[u]);
		}
		up[v + n][k] = max(up[epar][k], up[epar][k - 1] + a[v]);
	}
	ans = max({ans, up[v + n][B], dn[v][B], dn[v][B - 1] + a[cen]});

	for (int e : adj[v])
	{
		int u = efrom[e] ^ eto[e] ^ v;
		if (mark[u] || u == par) continue;
		dfs2(u, v, e);
	}
}

void solve(int r)
{
	dfs1(r, -1);
	int v = findcen(r, -1, subtree[r]);
	mark[v] = true;
	cen = v;

	for (int e : adj[v])
	{
		int u = efrom[e] ^ eto[e] ^ v;
		if (mark[u]) continue;
		FOR(k, 1, B + 1)
			up[e][k] = a[v] - p[u];
	}
	FOR(k, 1, B + 1) up[v + n][k] = a[v];
	ans = max(ans, a[v]);
	
	for (int e : adj[v])
	{
		int u = efrom[e] ^ eto[e] ^ v;
		if (mark[u]) continue;
		rt = u;
		dfs2(u, v, e);
	}

	for (int e : adj[v])
	{
		int u = efrom[e] ^ eto[e] ^ v;
		if (mark[u]) continue;
		for (int x : dfs_ord[u])
		{
			FOR(k, 0, B + 1)
				ans = max({ans, dn[x][k] + mxup[B - k], up[x + n][k] + mxdn[B - k]});
		}
		for (int x : dfs_ord[u])
			FOR(k, 0, B + 1)
			{
				mxdn[k] = max(mxdn[k], dn[x][k]);
				mxup[k] = max(mxup[k], up[x + n][k]);
			}

		for (int x : dfs_ord[u])
		{
			memset(up[x + n], 0, sizeof(up[x + n]));
			memset(dn[x], 0, sizeof(dn[x]));
			memset(up[_epar[x]], 0, sizeof(up[_epar[x]]));
		}
		dfs_ord[u].clear();
	}
	
	// clear stuff => dfs_ord, up, dn, mxdn, mxup
	memset(mxup, 0, sizeof(mxup));
	memset(mxdn, 0, sizeof(mxdn));

	for (int e : adj[v])
	{
		int u = efrom[e] ^ eto[e] ^ v;
		if (mark[u]) continue;
		solve(u);
	}
}

int32_t main(void)
{
	fast_io;
	cin >> n >> B;
	FOR(i, 1, n + 1) cin >> p[i];
	FOR(i, 1, n)
	{
		int x, y;
		cin >> x >> y;
		efrom[i] = x;
		eto[i] = y;
		adj[x].pb(i);
		adj[y].pb(i);
		a[x] += p[y];
		a[y] += p[x];
	}

	if (B == 0) return cout << "0\n", 0;

	solve(1);

	cout << ans << endl;
	
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5072 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5004 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5072 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5004 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 22 ms 7816 KB Output is correct
8 Correct 8 ms 7756 KB Output is correct
9 Correct 5 ms 7628 KB Output is correct
10 Correct 14 ms 7740 KB Output is correct
11 Correct 9 ms 7736 KB Output is correct
12 Correct 8 ms 7628 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4107 ms 283112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5072 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5004 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 22 ms 7816 KB Output is correct
8 Correct 8 ms 7756 KB Output is correct
9 Correct 5 ms 7628 KB Output is correct
10 Correct 14 ms 7740 KB Output is correct
11 Correct 9 ms 7736 KB Output is correct
12 Correct 8 ms 7628 KB Output is correct
13 Execution timed out 4107 ms 283112 KB Time limit exceeded
14 Halted 0 ms 0 KB -