Submission #961630

#	Time	Username	Problem	Language	Result	Execution time	Memory
961630		TAhmed33	Nestabilnost (COI23_nestabilnost)	C++98	41 / 100	150 ms	197312 KiB

code1

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 25;
typedef long long ll;
const ll inf = 1e14;
ll a[MAXN], f[MAXN], n;
vector <int> adj[MAXN];
bool vis[MAXN];
vector <int> ind;
void fix (int pos, int par) {
	ind.push_back(pos);
	for (int i = 0; i < (int)adj[pos].size(); i++) {
		if (adj[pos][i] == par) {
			adj[pos].erase(adj[pos].begin() + i);
		}
	}
	vector <int> g; 
	for (auto j : adj[pos]) {
		fix(j, pos);
		if (a[pos] + 1 == a[j] || a[j] == 0) {
			g.push_back(j);
		}
	}
	adj[pos] = g;
}
vector <ll> dfs (int pos) {
	vector <ll> dp(n + 1);
	vis[pos] = 1;
	for (int i = 1; i <= a[pos]; i++) dp[i] = inf;
	for (auto j : adj[pos]) {
		auto z = dfs(j);
		ll mn = inf;
		for (int u = 1; u <= n; u++) {
			mn = min(mn, f[u] + z[u]);
		}
		for (ll i = a[pos] + 1; i <= n; i++) {
			if (a[pos] != i - 1 && a[j] == 0) {
				dp[i] += mn;
			} else {
				dp[i] += min(mn, z[i]);
			}
		}
	}
	return dp;
}
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> f[i];
	for (int i = 1; i < n; i++) {
		int x, y; cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	fix(1, -1);
	for (int i = 1; i <= n; i++) {
		for (auto j : adj[i]) {
			assert(a[j] == 0 || a[i] + 1 == a[j]); 
		}
	}
	ll sum = 0;
	for (auto i : ind) {
		if (!vis[i]) {
			auto z = dfs(i);
			ll mn = inf;
			for (int j = 1; j <= n; j++) {
				mn = min(mn, f[j] + z[j]);
			}
			sum += mn;
		}
	}
	cout << sum << '\n';
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 20
• Subtask 3: 7 / 7
• Subtask 4: 22 / 22
• Subtask 5: 0 / 39