oj.uz

Submission #1060216

# Submission time Handle Problem Language Result Execution time Memory
1060216 2024-08-15T11:38:51 Z aymanrs Nestabilnost (COI23_nestabilnost) C++17
12 / 100
 122 ms 66136 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 && 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) 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 1368 KB Output is correct
2 Correct 3 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 114 ms 66044 KB Output is correct
2 Correct 114 ms 66128 KB Output is correct
3 Correct 118 ms 66136 KB Output is correct
4 Correct 119 ms 66132 KB Output is correct
5 Correct 118 ms 66128 KB Output is correct
6 Correct 108 ms 66132 KB Output is correct
7 Correct 122 ms 66128 KB Output is correct
8 Incorrect 111 ms 66128 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 1368 KB Output is correct
2 Correct 3 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 1 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 1368 KB Output is correct
2 Correct 3 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 114 ms 66044 KB Output is correct
8 Correct 114 ms 66128 KB Output is correct
9 Correct 118 ms 66136 KB Output is correct
10 Correct 119 ms 66132 KB Output is correct
11 Correct 118 ms 66128 KB Output is correct
12 Correct 108 ms 66132 KB Output is correct
13 Correct 122 ms 66128 KB Output is correct
14 Incorrect 111 ms 66128 KB Output isn't correct
15 Halted 0 ms 0 KB -