oj.uz

Submission #791678

# Submission time Handle Problem Language Result Execution time Memory
791678 2023-07-24T08:46:37 Z 이성호(#10048) Nestabilnost (COI23_nestabilnost) C++17
32 / 100
 313 ms 54992 KB 
#include <iostream>
#include <vector>
#define int long long
using namespace std;

vector<int> adj[300005];
int N, a[300005];
int f[300005];
int suf[300005];
vector<int> arr;
void dfs(int v, int p)
{
    arr.push_back(a[v]);
    for (int i:adj[v]) {
        if (i != p) dfs(i, v);
    }
}
int solve(int l, int r)
{
    vector<int> vc;
    for (int i = l; i <= r; i++) vc.push_back(arr[i]);
    int n = r - l + 1; //0~n-1
    vector<int> pk;
    for (int i = 1; i < n; i++) {
        if (vc[i] == 0) {
            pk.push_back(vc[i-1]+1);
        }
    }
    pk.push_back(vc[n-1]+1);
    vector<int> dp(pk.size()+1);
    dp[pk.size()] = 0;
    vector<int> nxt(pk.size());
    nxt[(int)pk.size()-1] = (int)pk.size() - 1;
    for (int i = (int)pk.size() - 2; i >= 0; i--) {
        if (pk[i] == pk[i+1]) nxt[i] = nxt[i+1];
        else nxt[i] = i;
    }
    for (int i = (int)pk.size() - 1; i >= 0; i--) {
        dp[i] = dp[i+1] + suf[pk[i]];
        int p = nxt[i];
        if (p + 1 < (int)pk.size() && pk[p] > pk[p+1]) dp[i] = min(dp[i], min(dp[p+1], dp[p+2]) + f[pk[i]]);
        else dp[i] = min(dp[i], dp[p+1] + f[pk[i]]);
    }
    return dp[0];
}
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);
    }
    suf[N] = f[N];
    for (int i = N - 1; i >= 1; i--) {
        suf[i] = min(suf[i+1], f[i]);
    }
    dfs(1, 0);
    int prv = 0;
    int ans = 0;
    for (int i = 1; i < N; i++) {
        if (arr[i] != arr[i-1] + 1 && arr[i]) {
            ans += solve(prv, i-1);
            prv = i;
        }
    }
    ans += solve(prv, N-1);
    cout << ans << '\n';
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7984 KB Output is correct
2 Correct 8 ms 7976 KB Output is correct
3 Correct 8 ms 8020 KB Output is correct
4 Correct 8 ms 8084 KB Output is correct
5 Correct 8 ms 8044 KB Output is correct
6 Correct 8 ms 8024 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 49752 KB Output is correct
2 Correct 300 ms 46308 KB Output is correct
3 Correct 305 ms 54592 KB Output is correct
4 Correct 313 ms 54992 KB Output is correct
5 Correct 296 ms 54000 KB Output is correct
6 Correct 299 ms 49596 KB Output is correct
7 Correct 293 ms 48292 KB Output is correct
8 Correct 294 ms 48028 KB Output is correct
9 Correct 291 ms 47936 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7984 KB Output is correct
2 Correct 8 ms 7976 KB Output is correct
3 Correct 8 ms 8020 KB Output is correct
4 Correct 8 ms 8084 KB Output is correct
5 Correct 8 ms 8044 KB Output is correct
6 Correct 8 ms 8024 KB Output is correct
7 Incorrect 3 ms 7260 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7984 KB Output is correct
2 Correct 8 ms 7976 KB Output is correct
3 Correct 8 ms 8020 KB Output is correct
4 Correct 8 ms 8084 KB Output is correct
5 Correct 8 ms 8044 KB Output is correct
6 Correct 8 ms 8024 KB Output is correct
7 Correct 305 ms 49752 KB Output is correct
8 Correct 300 ms 46308 KB Output is correct
9 Correct 305 ms 54592 KB Output is correct
10 Correct 313 ms 54992 KB Output is correct
11 Correct 296 ms 54000 KB Output is correct
12 Correct 299 ms 49596 KB Output is correct
13 Correct 293 ms 48292 KB Output is correct
14 Correct 294 ms 48028 KB Output is correct
15 Correct 291 ms 47936 KB Output is correct
16 Incorrect 3 ms 7260 KB Output isn't correct
17 Halted 0 ms 0 KB -