oj.uz

Submission #888232

# Submission time Handle Problem Language Result Execution time Memory
888232 2023-12-16T15:01:21 Z Markadiusz Chase (CEOI17_chase) C++17
40 / 100
 375 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);

    int n, V;
    cin >> n >> V;
	if (V == 0) {
		cout << 0 << '\n';
		return 0;
	}
    vector<int> P(n);
    REP(i, n)
        cin >> P[i];
    vector<vector<int>> graph(n);
	vector<LL> sum_neighbours(n);
    REP(i, n - 1) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
		sum_neighbours[a] += P[b];
		sum_neighbours[b] += P[a];
    }
	debug(n, V, P, graph, sum_neighbours);

#ifdef LOCAL
	const LL INF = 100;
#else
	const LL INF = 1e18;
#endif
	using Info = vector<array<LL, 2>>;
	Info blank(V + 1);
	FOR(i, 0, V) {
		blank[i][0] = blank[i][1] = 0;
	}
	blank[0][1] = -INF;
	auto make_info = [&](int v) {
		Info ret = blank;
		ret[1][1] = sum_neighbours[v];
		return ret;
	};
	auto extend_info = [&](Info h, int v) -> Info {
		Info ret = blank;
		FOR(i, 0, V) {
			ret[i][0] = max(h[i][0], h[i][1] - P[v]);
		}
		FOR(i, 1, V) {
			ret[i][1] = ret[i - 1][0] + sum_neighbours[v];
		}
		debug(h, v, P[v], ret);
		return ret;
	};
	auto get_better = [&](Info a, Info b) {
		FOR(i, 0, V)
			REP(j, 2)
				a[i][j] = max(a[i][j], b[i][j]);
		return a;
	};
	auto get_ans = [&](Info a) {
		LL ans = 0;
		FOR(i, 0, V)
			REP(j, 2)
				ans = max(ans, a[i][j]);
		return ans;
	};

	vector<vector<Info>> pref(n), suff(n);
	function<void(int, int)> init_dfs = [&](int v, int p) {
		auto it = find(graph[v].begin(), graph[v].end(), p);
		if (it != graph[v].end())
			graph[v].erase(it);
		debug(v, p, graph[v]);

		for (auto x : graph[v])
			init_dfs(x, v);

		const int s = ssize(graph[v]);
		pref[v].resize(s + 1, blank);
		suff[v].resize(s + 1, blank);
		pref[v][0] = suff[v][s] = make_info(v);
		FOR(i, 1, s) {
			const int x = graph[v][i - 1];
			pref[v][i] = get_better(pref[v][i - 1], extend_info(pref[x].back(), v));
		}
		for (int i = s - 1; i >= 0; --i) {
			const int x = graph[v][i];
			suff[v][i] = get_better(suff[v][i + 1], extend_info(pref[x].back(), v));
		}
	};
	init_dfs(0, -1);

#ifdef DEBUG
	REP(i, n)
		debug(i, pref[i], suff[i]);
#endif

	LL ans = 0;
	function<void(int, Info)> dfs = [&](int v, Info value_from_parent) {
		Info best = get_better(extend_info(value_from_parent, v), pref[v].back());
		ans = max(ans, get_ans(best));
		debug(v, value_from_parent, best);

		REP(i, ssize(graph[v])) {
			auto value_for_child = extend_info(value_from_parent, v);
			value_for_child = get_better(value_for_child, pref[v][i]);
			value_for_child = get_better(value_for_child, suff[v][i + 1]);
			dfs(graph[v][i], value_for_child);
		}
	};
	dfs(0, blank);
	cout << ans << '\n';
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 11 ms 9564 KB Output is correct
8 Correct 2 ms 1232 KB Output is correct
9 Correct 1 ms 988 KB Output is correct
10 Correct 6 ms 7004 KB Output is correct
11 Correct 3 ms 2648 KB Output is correct
12 Correct 2 ms 1232 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 375 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 11 ms 9564 KB Output is correct
8 Correct 2 ms 1232 KB Output is correct
9 Correct 1 ms 988 KB Output is correct
10 Correct 6 ms 7004 KB Output is correct
11 Correct 3 ms 2648 KB Output is correct
12 Correct 2 ms 1232 KB Output is correct
13 Runtime error 375 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -