oj.uz

Submission #954931

# Submission time Handle Problem Language Result Execution time Memory
954931 2024-03-28T20:33:17 Z Lukap Nestabilnost (COI23_nestabilnost) C++14
41 / 100
 201 ms 216840 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e3 + 500;
const ll INF = 1e18;

int n;
int val[MAXN], fk[MAXN];
vector<int> susjedi[MAXN], v;
int d[MAXN], parent[MAXN];
ll dp[MAXN][MAXN], najm[MAXN];

void dfs (int x) {
    for (auto nx: susjedi[x]) {
        if (parent[x] == nx) continue;
        d[nx] = d[x] + 1;
        parent[nx] = x;
        dfs (nx);
    }
}

bool cmp (int x, int y) {
    return d[x] > d[y];
}

int main () {
    ios_base::sync_with_stdio (false);
    cin.tie (0);

    cin >> n;
    for (int i = 0; i < n; i++) cin >> val[i];
    for (int i = 0; i < n; i++) cin >> fk[i];

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        susjedi[a - 1].push_back (b - 1);
        susjedi[b - 1].push_back (a - 1);
    }

    dfs (0);
    for (int i = 0; i < n; i++) v.push_back (i);
    sort (v.begin (), v.end (), cmp);

    for (auto x: v) {
        for (int i = 0; i < n; i++) {
            if (val[x] > i) {
                dp[x][i] = INF;
                continue;
            }
            dp[x][i] = fk[i];
            for (auto nx: susjedi[x]) {
                if (parent[x] == nx) continue;
                if ((val[x] + 1 == val[nx] && val[nx] <= i) || (val[x] == i && val[nx] == 0)) dp[x][i] += min (dp[nx][i] - fk[i], najm[nx]);
                else dp[x][i] += najm[nx];
            }
        }
        najm[x] = INF;
        for (int i = 0; i < n; i++) najm[x] = min (najm[x], dp[x][i]);
    }

    cout << najm[0];

    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 216660 KB Output is correct
2 Correct 143 ms 216756 KB Output is correct
3 Correct 134 ms 216800 KB Output is correct
4 Correct 133 ms 216792 KB Output is correct
5 Correct 132 ms 216712 KB Output is correct
6 Correct 134 ms 216588 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 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 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2656 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 216660 KB Output is correct
2 Correct 143 ms 216756 KB Output is correct
3 Correct 134 ms 216800 KB Output is correct
4 Correct 133 ms 216792 KB Output is correct
5 Correct 132 ms 216712 KB Output is correct
6 Correct 134 ms 216588 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2656 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 149 ms 216608 KB Output is correct
15 Correct 148 ms 216540 KB Output is correct
16 Correct 158 ms 216508 KB Output is correct
17 Correct 151 ms 216656 KB Output is correct
18 Correct 146 ms 216480 KB Output is correct
19 Correct 146 ms 216476 KB Output is correct
20 Correct 133 ms 211228 KB Output is correct
21 Correct 140 ms 216752 KB Output is correct
22 Correct 136 ms 215888 KB Output is correct
23 Correct 137 ms 216400 KB Output is correct
24 Correct 156 ms 216840 KB Output is correct
25 Correct 137 ms 211940 KB Output is correct
26 Correct 141 ms 216640 KB Output is correct
27 Correct 140 ms 216660 KB Output is correct

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 216660 KB Output is correct
2 Correct 143 ms 216756 KB Output is correct
3 Correct 134 ms 216800 KB Output is correct
4 Correct 133 ms 216792 KB Output is correct
5 Correct 132 ms 216712 KB Output is correct
6 Correct 134 ms 216588 KB Output is correct
7 Incorrect 1 ms 600 KB Output isn't correct
8 Halted 0 ms 0 KB -