oj.uz

Submission #884405

# Submission time Handle Problem Language Result Execution time Memory
884405 2023-12-07T09:49:45 Z noiaint Nestabilnost (COI23_nestabilnost) C++17
41 / 100
 114 ms 197364 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 5e3 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n;
vector<int> adj[N];
int a[N];
int fk[N];
int f[N][N];
int ans[N];

void dfs(int u, int p) {
    for (int i = a[u] + 1; i <= n; ++i) f[u][i] = fk[i];

    for (int v : adj[u]) if (v != p) {
        dfs(v, u);
//        for (int k = a[u] + 1; k <= n; ++k) {
//            if (a[v] == (a[u] + 1) % k) f[u][k] += min(ans[v], f[v][k] - fk[k]);
//            else f[u][k] += ans[v];
//        }

        for (int k = a[u] + 1; k <= n; ++k) {
            if (k <= a[v]) f[u][k] += ans[v];
            else if (a[v] == 0 && a[u] + 1 == k) f[u][k] += min(ans[v], f[v][k] - fk[k]);
            else if (a[v] > 0 && a[u] + 1 == a[v]) f[u][k] += min(ans[v], f[v][k] - fk[k]);
            else f[u][k] += ans[v];
        }
    }

    ans[u] = *min_element(f[u] + a[u] + 1, f[u] + n + 1);
}

void process() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> fk[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 << ans[1];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #else
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    #endif

    int tc = 1;
    // cin >> tc;

    while (tc--) {
        process();
    }

    return 0;
}

/*

*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 197036 KB Output is correct
2 Correct 85 ms 197212 KB Output is correct
3 Correct 78 ms 197204 KB Output is correct
4 Correct 88 ms 197272 KB Output is correct
5 Correct 82 ms 197364 KB Output is correct
6 Correct 87 ms 197196 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 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 197036 KB Output is correct
2 Correct 85 ms 197212 KB Output is correct
3 Correct 78 ms 197204 KB Output is correct
4 Correct 88 ms 197272 KB Output is correct
5 Correct 82 ms 197364 KB Output is correct
6 Correct 87 ms 197196 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 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 95 ms 196764 KB Output is correct
15 Correct 97 ms 196648 KB Output is correct
16 Correct 100 ms 196724 KB Output is correct
17 Correct 95 ms 196664 KB Output is correct
18 Correct 95 ms 196816 KB Output is correct
19 Correct 101 ms 196944 KB Output is correct
20 Correct 88 ms 193936 KB Output is correct
21 Correct 92 ms 196800 KB Output is correct
22 Correct 89 ms 196680 KB Output is correct
23 Correct 91 ms 196728 KB Output is correct
24 Correct 90 ms 196908 KB Output is correct
25 Correct 87 ms 192852 KB Output is correct
26 Correct 90 ms 196692 KB Output is correct
27 Correct 91 ms 196692 KB Output is correct

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 197036 KB Output is correct
2 Correct 85 ms 197212 KB Output is correct
3 Correct 78 ms 197204 KB Output is correct
4 Correct 88 ms 197272 KB Output is correct
5 Correct 82 ms 197364 KB Output is correct
6 Correct 87 ms 197196 KB Output is correct
7 Incorrect 1 ms 600 KB Output isn't correct
8 Halted 0 ms 0 KB -