oj.uz

Submission #113904

# Submission time Handle Problem Language Result Execution time Memory
113904 2019-05-29T07:24:52 Z MAMBA Chase (CEOI17_chase) C++17
0 / 100
 245 ms 104636 KB 
#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef complex<ld> point;
typedef pair<ld , ld> pld;
typedef vector<ll> vi;

inline void fileIO(string s) {
	//	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }

constexpr int N = 1e5 + 10;
constexpr int MOD = 1e9 + 7;

template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }

int n;
ll dp_up[100][N], dp_down[100][N], v2, p[N], p2[N];
vi adj[N];

void dfs_down(int v, int par = 0) {
	dp_down[0][v] = p2[v] - p[v];
	for (auto e : adj[v]) 
		if (e ^ par) {
			dfs_down(e , v);
			rep(j , 1 , v2)
				smax(dp_down[j][v] , dp_down[j - 1][e] + p2[v] - 2 * p[v]);
		}
}

ll junk[100];
void dfs_up(int v, int par = 0) {
	auto f = [v , par]() -> void {
		rep(i , 0 , v2)
			junk[i] = dp_up[i][v];
		for (auto e : adj[v]) 
			if (e ^ par) {
				dp_up[0][e] = dp_down[0][e];
				rep(j , 1 , v2)
					smax(dp_up[j][e] , junk[j - 1] + p2[e] - 2 * p[e]);
				rep(j , 0 , v2 - 1) 
					smax(junk[j + 1] , dp_down[e][j] + p2[v] - 2 * p[v]);
			}
	};
	f();
	reverse(all(adj[v]));
	f();
	for (auto e : adj[v])
		if (e ^ par)
			dfs_up(e , v);
}

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

	cin >> n >> v2;

	if (v2 == 0) return cout << 0 << endl, 0;

	rep(i , 1 , n + 1) {
		cin >> p[i];
		p2[i] = p[i];
	}
	rep(i , 1 , n) {
		int u , v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
		p2[u] += p[v];
		p2[v] += p[u];
	}

	dfs_down(1);
	dp_up[0][1] = dp_down[0][1];
	dfs_up(1);

	cout << max(*max_element(dp_down[v2 - 1] , dp_down[v2 - 1] + 1 + n) , *max_element(dp_up[v2 - 1], dp_up[v2 - 1] + n + 1)) << endl;

	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Incorrect 4 ms 2688 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Incorrect 4 ms 2688 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 245 ms 104636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Incorrect 4 ms 2688 KB Output isn't correct
3 Halted 0 ms 0 KB -