Submission #1129720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129720		gyg	Nestabilnost (COI23_nestabilnost)	C++20	0 / 100	313 ms	47248 KiB

code1

#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.push_back({cl, u});
            } else {
                cls.clear();
                cls.push_back({-1, u});
            }
        }
        if (cls.size() >= 2) 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]);

    // for (int u = 1; u <= n; u++) {
    //     cout << u << ": ";
    //     for (pii x : trns[u]) cout << x.fir << "," << x.sec << " ";
    //     cout << endl;
    // }
}

arr<int, N> dp;
void cmp() {
    for (int u = 1; u <= n; u++) {
        dp[u] = INF;
        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 << u << ": " << dp[u] << endl;
    }
    cout << dp[n] << endl;
}

signed main() {
    // freopen("a.in", "r", stdin);
    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();
}

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