oj.uz

Submission #884406

# Submission time Handle Problem Language Result Execution time Memory
884406 2023-12-07T09:50:01 Z noiaint Nestabilnost (COI23_nestabilnost) C++17
41 / 100
 175 ms 197108 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];
        }
    }

    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 162 ms 196944 KB Output is correct
2 Correct 162 ms 197008 KB Output is correct
3 Correct 147 ms 195924 KB Output is correct
4 Correct 162 ms 197108 KB Output is correct
5 Correct 162 ms 196948 KB Output is correct
6 Correct 162 ms 196956 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 196944 KB Output is correct
2 Correct 162 ms 197008 KB Output is correct
3 Correct 147 ms 195924 KB Output is correct
4 Correct 162 ms 197108 KB Output is correct
5 Correct 162 ms 196948 KB Output is correct
6 Correct 162 ms 196956 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2652 KB Output is correct
12 Correct 0 ms 2652 KB Output is correct
13 Correct 0 ms 2652 KB Output is correct
14 Correct 174 ms 196536 KB Output is correct
15 Correct 173 ms 196836 KB Output is correct
16 Correct 167 ms 196692 KB Output is correct
17 Correct 172 ms 196692 KB Output is correct
18 Correct 175 ms 196640 KB Output is correct
19 Correct 174 ms 196824 KB Output is correct
20 Correct 167 ms 193664 KB Output is correct
21 Correct 173 ms 196688 KB Output is correct
22 Correct 174 ms 196948 KB Output is correct
23 Correct 172 ms 196432 KB Output is correct
24 Correct 172 ms 196644 KB Output is correct
25 Correct 163 ms 192852 KB Output is correct
26 Correct 168 ms 196692 KB Output is correct
27 Correct 170 ms 196728 KB Output is correct

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 196944 KB Output is correct
2 Correct 162 ms 197008 KB Output is correct
3 Correct 147 ms 195924 KB Output is correct
4 Correct 162 ms 197108 KB Output is correct
5 Correct 162 ms 196948 KB Output is correct
6 Correct 162 ms 196956 KB Output is correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -