Submission #1129713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129713		gyg	Nestabilnost (COI23_nestabilnost)	C++20	12 / 100	442 ms	197136 KiB

code1

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define arr array 
#define vec vector 
const int N = 5e3 + 5, INF = 1e18;

int n;
arr<int, N> vl, cst;
arr<vec<int>, N> adj;

arr<arr<int, N>, N> dp;
arr<int, N> mn;
void dfs(int u = 1, int pr = -1) {
    for (int v : adj[u])
        if (v != pr) dfs(v, u);

    mn[u] = INF;
    for (int c = 1; c <= n; c++) {
        for (int v : adj[u]) {
            if (v == pr) continue;
            int tk = ((vl[u] + 1) % c == vl[v]) ? dp[v][c] : INF;
            int lv = mn[v];
            dp[u][c] += min(tk, lv);
        }
        if (c < vl[u] + 1) dp[u][c] = INF;
        // cout << u << " " << c << ": " << dp[u][c] << endl;
        mn[u] = min(mn[u], dp[u][c] + cst[c]);
    }
}

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);
    }
    assert(n == 1 || (adj[1].size() == 1 && adj[n].size() == 1));

    dfs();

    int ans = INF;
    for (int c = 1; c <= n; c++) ans = min(ans, dp[1][c] + cst[c]);
    cout << ans << endl;
}

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