oj.uz

Submission #888234

# Submission time Handle Problem Language Result Execution time Memory
888234 2023-12-16T15:24:37 Z Markadiusz Chase (CEOI17_chase) C++17
40 / 100
 839 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<Info> best(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]);
		vector<Info> pref(s + 1, blank), suff(s + 1, blank);

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

	LL ans = 0;
	function<void(int, Info)> dfs = [&](int v, Info value_from_parent) {
		const int s = ssize(graph[v]);
		vector<Info> pref(s + 1, blank), suff(s + 1, blank);

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

		Info val = get_better(extend_info(value_from_parent, v), best[v]);
		ans = max(ans, get_ans(val));
		debug(v, value_from_parent, val);

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 7 ms 5720 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 6 ms 2140 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 2 ms 604 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 511772 KB Output is correct
2 Correct 806 ms 509812 KB Output is correct
3 Runtime error 693 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 7 ms 5720 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 6 ms 2140 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 839 ms 511772 KB Output is correct
14 Correct 806 ms 509812 KB Output is correct
15 Runtime error 693 ms 524288 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -