Submission #1186628

#TimeUsernameProblemLanguageResultExecution timeMemory
1186628vitoNestabilnost (COI23_nestabilnost)C++17
0 / 100
222 ms45080 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define arr array 
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 3e5 + 5, INF = 1e18;
int n;
arr<int, N> vl, cst;
arr<vec<int>, N> adj;
arr<vec<pii>, N> trns;
arr<int, N> mn;
void prcmp() {
    vec<pii> cls = {{-1, 1}};
    for (int u = 1; u <= n; u++) {
        if (u != 1 && vl[u - 1] + 1 != vl[u]) {
            if (vl[u] == 0) {
                int cl = vl[u - 1] + 1;
                if (cls.size() && cls.back().fir == cl) cls.back().sec = u;
                else cls.push_back({cl, u});
            } else {
                cls.clear();
                cls.push_back({-1, u});
            }
        }
        if (cls.size() >= 2 && cls.back().fir >= vl[u] + 1) 
            trns[u].push_back({cls.back().fir, cls[cls.size() - 2].sec});
        trns[u].push_back({-1, cls.back().sec});
    }

    mn[n + 1] = INF;
    for (int c = n; c >= 1; c--) mn[c] = min(mn[c + 1], cst[c]);
}
arr<int, N> dp;
void cmp() {
    for (int u = 1; u <= n; u++) {
        dp[u] = INF;
        assert(trns[u].size()<=1);
        for (pii x : trns[u]) {
            int nw_dp = dp[x.sec - 1] + ((x.fir == -1) ? mn[vl[u] + 1] : cst[x.fir]);
            dp[u] = min(dp[u], nw_dp);
        }
    }
    cout << dp[n] << endl;
}
signed main() {
    cin >> n;
    for (int u = 1; u <= n; u++) cin >> vl[u];
    for (int c = 1; c <= n; c++) cin >> cst[c];
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v), adj[v].push_back(u);
        }
    prcmp();
    cmp();
}
#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...