oj.uz

Submission #1060229

# Submission time Handle Problem Language Result Execution time Memory
1060229 2024-08-15T11:44:23 Z aymanrs Nestabilnost (COI23_nestabilnost) C++17
12 / 100
 121 ms 66184 KB 
#include<bits/stdc++.h>
using namespace std;
vector<int> cost, mic;int N;
struct node {
    vector<long long> dp;
    long long lock=-1,free = -1;
    vector<node*> l;
    int a;
};
// void dfs(node* n, node* p){
//     for(node* c : n->l) if(c!=p) dfs(c,n);
//     n->dp.resize(N+1);
//     n->free = LONG_LONG_MAX;
//     for(int k = n->a+1;k <= N;k++){
//         n->dp[k] = cost[k];
//         for(node* c : n->l){
//             if(c==p) continue;
//             if(!c->a){
//                 if(k == n->a+1) n->dp[k] += min(c->dp[k]-cost[k], c->free);
//                 else n->dp[k] += c->free;
//             } else if(c->a == n->a+1){
//                 if(k>c->a) n->dp[k] += min(c->dp[k]-cost[k], c->free);
//                 else n->dp[k] += c->free;
//             } else n->dp[k] += c->free;
//         }
//         n->free = min(n->free, n->dp[k]);
//     }
// }
long long dfs(node* n, node* p, int l, int r){
    if(l==r && r<N && n->lock != -1) return n->lock;
    if(l==1&&r==N&&n->free != -1) return n->free;
    long long ans = 0;
    for(node* c : n->l) if(c!=p) {
        if(!c->a){
            if(r<n->a+1 || n->a+1 < l){
                if(r==N) ans += mic[l]+dfs(c, n, 1, N);
                else ans += cost[l]+dfs(c, n, 1,N);
            } else {
                if(l==r) ans += dfs(c, n, l,r);
                else ans += min(dfs(c, n, n->a+1,n->a+1), mic[l]+dfs(c,n,1,N));
            }
        } else if(c->a == n->a+1){
            if(r <= c->a) ans += cost[r]+dfs(c, n, 1, N);
            else ans += dfs(c, n, max(l,c->a+1),r);
        } else {
            if(l==r) ans += cost[l]+dfs(c,n, 1, N);
            else ans += mic[l]+dfs(c,n,1,N);
        }
    }
    if(!ans) {
        if(l==r) ans = cost[l];
        else ans = mic[l];
    }
    if(l==r&&r<N) n->lock=ans;
    if(l==1&&r==N) n->free=ans;
    return ans;
}
void solve(){
    int n;cin >> n;
    N=n;
    node g[n+1];
    cost.resize(n+1);
    mic.resize(n+1);
    for(int i = 1;i <= n;i++) cin >> g[i].a;
    for(int i = 1;i <= n;i++) cin >> cost[i];
    for(int i = n;i >= 1;i--){
        mic[i] = cost[i];
        if(i < n) mic[i] = min(mic[i],mic[i+1]);
    }
    for(int i = 0;i < n-1;i++){
        int u,v;cin >> u >> v;
        g[u].l.push_back(&g[v]);
        g[v].l.push_back(&g[u]);
    }
    cout << dfs(&g[1], NULL, 1, N) << '\n';
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

Subtask #1
12.0 / 12.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 66136 KB Output is correct
2 Correct 118 ms 65960 KB Output is correct
3 Correct 120 ms 66116 KB Output is correct
4 Correct 121 ms 66176 KB Output is correct
5 Correct 112 ms 66128 KB Output is correct
6 Correct 117 ms 66128 KB Output is correct
7 Correct 114 ms 66184 KB Output is correct
8 Incorrect 119 ms 66008 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1372 KB Output is correct
2 Correct 2 ms 1372 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 2 ms 1372 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1372 KB Output is correct
2 Correct 2 ms 1372 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 2 ms 1372 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 118 ms 66136 KB Output is correct
8 Correct 118 ms 65960 KB Output is correct
9 Correct 120 ms 66116 KB Output is correct
10 Correct 121 ms 66176 KB Output is correct
11 Correct 112 ms 66128 KB Output is correct
12 Correct 117 ms 66128 KB Output is correct
13 Correct 114 ms 66184 KB Output is correct
14 Incorrect 119 ms 66008 KB Output isn't correct
15 Halted 0 ms 0 KB -