oj.uz

Submission #113931

# Submission time Handle Problem Language Result Execution time Memory
113931 2019-05-29T08:48:05 Z MAMBA Chase (CEOI17_chase) C++17
20 / 100
 742 ms 329012 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[N][2][101], dp_down[N][2][101], v2, p[N], p2[N];
vi adj[N];

inline void update(ll A[][101] , ll B[][101] ,int so ,int sy) {
	rep(j , 0 , v2) {
		smax(A[0][j] , B[0][j]);
		smax(A[0][j] , B[1][j] - p[so]);
		if (j) {
			smax(A[1][j] , B[0][j - 1] + p2[so]);
			smax(A[1][j] , B[1][j - 1] + p2[so] - p[so]);
		}
	}
}

void dfs_down(int v, int par = 0) {
	dp_down[v][1][0] = dp_up[v][1][0] = -1e18;
	rep(i , 1 , v2)
		dp_down[v][1][i] = dp_up[v][1][i] = p2[v];
	for (auto e : adj[v]) 
		if (e ^ par) {
			dfs_down(e , v);
			update(dp_down[v] , dp_down[e] , v , e);
		}
}

ll junk[2][101];
void dfs_up(int v, int par = 0) {
	auto f = [v , par]() -> void {
		memcpy(junk , dp_up[v] , sizeof(dp_up[v]));		
		for (auto e : adj[v]) 
			if (e ^ par) {
				update(dp_up[e] , junk , e , v);
				update(junk , dp_down[e] , v , e);
			}
	};
	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;
	v2++;

	rep(i , 1 , n + 1) 
		cin >> 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);

	dfs_up(1);

	ll res = 0;
	rep(i , 1, n + 1)
		smax(res , max(dp_up[i][1][v2 - 1] , dp_up[i][0][v2 - 1]));
	cout << res << endl;

	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 742 ms 329012 KB Output isn't correct
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 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Incorrect 10 ms 6016 KB Output isn't correct
8 Halted 0 ms 0 KB -