oj.uz

Submission #791714

# Submission time Handle Problem Language Result Execution time Memory
791714 2023-07-24T09:01:29 Z 이성호(#10048) Nestabilnost (COI23_nestabilnost) C++17
41 / 100
 250 ms 197044 KB 
#include <iostream>
#include <vector>
#define int long long
using namespace std;
int dp[5005][5005];
int tot[5005];
int f[5005];
int N;
vector<int> adj[5005];
int a[5005];
const int inf = 1e18;
void dfs(int v, int p)
{
    for (int i:adj[v]) {
        if (i != p) {
            dfs(i, v);
        }
    }
    for (int i = 1; i <= a[v]; i++) dp[v][i] = inf;
    for (int i:adj[v]) {
        if (i == p) continue;
        for (int k = a[v] + 1; k <= N; k++) {
            if (a[v] < k && a[i] == (a[v] + 1) % k) {
                dp[v][k] += min(tot[i], dp[i][k]);
            }
            else {
                dp[v][k] += tot[i];
            }
        }
    }
    tot[v] = inf;
    for (int i = 1; i <= N; i++) {
        tot[v] = min(tot[v], dp[v][i] + f[i]);
    }
}
signed main()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> a[i];
    for (int i = 1; i <= N; i++) cin >> f[i];
    for (int i = 1; i < N; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    cout << tot[1] << endl;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 196984 KB Output is correct
2 Correct 240 ms 196956 KB Output is correct
3 Correct 230 ms 196976 KB Output is correct
4 Correct 230 ms 197036 KB Output is correct
5 Correct 244 ms 197044 KB Output is correct
6 Correct 250 ms 197036 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 196984 KB Output is correct
2 Correct 240 ms 196956 KB Output is correct
3 Correct 230 ms 196976 KB Output is correct
4 Correct 230 ms 197036 KB Output is correct
5 Correct 244 ms 197044 KB Output is correct
6 Correct 250 ms 197036 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 0 ms 468 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 219 ms 106780 KB Output is correct
15 Correct 205 ms 107700 KB Output is correct
16 Correct 204 ms 113064 KB Output is correct
17 Correct 209 ms 107884 KB Output is correct
18 Correct 197 ms 107544 KB Output is correct
19 Correct 206 ms 116432 KB Output is correct
20 Correct 192 ms 106676 KB Output is correct
21 Correct 213 ms 106908 KB Output is correct
22 Correct 201 ms 106780 KB Output is correct
23 Correct 204 ms 105932 KB Output is correct
24 Correct 205 ms 119008 KB Output is correct
25 Correct 203 ms 117116 KB Output is correct
26 Correct 202 ms 120944 KB Output is correct
27 Correct 205 ms 125984 KB Output is correct

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 196984 KB Output is correct
2 Correct 240 ms 196956 KB Output is correct
3 Correct 230 ms 196976 KB Output is correct
4 Correct 230 ms 197036 KB Output is correct
5 Correct 244 ms 197044 KB Output is correct
6 Correct 250 ms 197036 KB Output is correct
7 Incorrect 3 ms 468 KB Output isn't correct
8 Halted 0 ms 0 KB -