Submission #884405

#TimeUsernameProblemLanguageResultExecution timeMemory
884405noiaintNestabilnost (COI23_nestabilnost)C++17
41 / 100
114 ms197364 KiB
#include <bits/stdc++.h> #define int long long using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif #define file "" #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define bit(x) (1LL << (x)) #define getbit(x, i) (((x) >> (i)) & 1) #define popcount __builtin_popcountll mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return l + rd() % (r - l + 1); } const int N = 5e3 + 5; const int mod = (int)1e9 + 7; // 998244353; const int lg = 25; // lg + 1 const int oo = 1e9; const long long ooo = 1e18; template<class X, class Y> bool mini(X &a, Y b) { return a > b ? (a = b, true) : false; } template<class X, class Y> bool maxi(X &a, Y b) { return a < b ? (a = b, true) : false; } void add(int &a, int b) { a += b; if (a >= mod) a -= mod; if (a < 0) a += mod; } int n; vector<int> adj[N]; int a[N]; int fk[N]; int f[N][N]; int ans[N]; void dfs(int u, int p) { for (int i = a[u] + 1; i <= n; ++i) f[u][i] = fk[i]; for (int v : adj[u]) if (v != p) { dfs(v, u); // for (int k = a[u] + 1; k <= n; ++k) { // if (a[v] == (a[u] + 1) % k) f[u][k] += min(ans[v], f[v][k] - fk[k]); // else f[u][k] += ans[v]; // } for (int k = a[u] + 1; k <= n; ++k) { if (k <= a[v]) f[u][k] += ans[v]; else if (a[v] == 0 && a[u] + 1 == k) f[u][k] += min(ans[v], f[v][k] - fk[k]); else if (a[v] > 0 && a[u] + 1 == a[v]) f[u][k] += min(ans[v], f[v][k] - fk[k]); else f[u][k] += ans[v]; } } ans[u] = *min_element(f[u] + a[u] + 1, f[u] + n + 1); } void process() { cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) cin >> fk[i]; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } dfs(1, 0); cout << ans[1]; } signed main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); #else // freopen(file".inp", "r", stdin); // freopen(file".out", "w", stdout); #endif int tc = 1; // cin >> tc; while (tc--) { process(); } return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...