Submission #1191308

#TimeUsernameProblemLanguageResultExecution timeMemory
1191308keremNestabilnost (COI23_nestabilnost)C++20
12 / 100
125 ms197076 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int ll #define fr first #define sc second #define pb push_back #define endl "\n" #define all(x) x.begin(),x.end() #define sp << " " << #define inf 1e15 #define N 5000 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef tuple<int,int,int> tiii; typedef pair<int,int> pii; int n,a[N+5],f[N+5],d[N+5][N+5]; vector<int> g[N+5]; int dfs(int x,int ata){ for(int i=a[x]+1;i<=n;i++) d[x][i]=f[i]; for(auto c:g[x]){ if(c==ata) continue; int t=dfs(c,x); if(a[x]+1==a[c]){ for(int i=a[x]+2;i<=n;i++) d[x][i]+=d[c][i]-f[i]; d[x][a[x]+1]+=t; } else if(a[c]==0){ for(int i=a[x]+2;i<=n;i++) d[x][i]+=t; d[x][a[x]+1]+=d[c][a[x]+1]-f[a[x]+1]; } else{ for(int i=a[x]+1;i<=n;i++) d[x][i]+=t; } } int ans=inf; for(int i=a[x]+1;i<=n;i++) ans=min(ans,d[x][i]); return ans; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); 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; g[x].pb(y); g[y].pb(x); } cout << dfs(1,0) << endl; }
#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...