Submission #1129704

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1129704	2024-12-26 07:38:59	gyg	Nestabilnost (COI23_nestabilnost)	C++20	41 / 100	431 ms	197144 KiB

code1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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]);
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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