Submission #1190954

#TimeUsernameProblemLanguageResultExecution timeMemory
1190954keremNestabilnost (COI23_nestabilnost)C++20
0 / 100
30 ms14400 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 300000 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],pre[N+5],ind[N+5]; vector<int> g[N+5]; pii End; void dfs(int x,int ata,int k){ ind[k]=x; int c=0; for(auto i:g[x]){ if(i==ata) continue; c=i; dfs(i,x,k+1); if(a[x]==a[i]-1) d[x]=d[i]; else d[x]=d[i]+pre[a[x]+1]; } if(a[x]==a[c]-1) return; if(!c){ End.fr=0; End.sc=a[x]+1; return; } if(a[c] || End.sc>a[x]+1){ End.fr=c; End.sc=a[x]+1; return; } if(End.sc==a[x]+1) d[x]=min(d[x],f[a[x]+1]+d[End.fr]); else if(End.sc<a[x]+1){ d[x]=min(d[x],f[a[x]+1]+d[ind[k+End.sc+1]]); End.fr=ind[k+End.sc+1]; End.sc=a[x]+1; } } 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]; pre[n]=f[n]; for(int i=n-1;i>=1;i++) pre[i]=min(f[i],pre[i+1]); for(int i=1;i<n;i++){ int x,y; cin >> x >> y; g[x].pb(y); g[y].pb(x); } dfs(1,0,1); cout << d[1]; }
#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...