oj.uz

Submission #1060157

# Submission time Handle Problem Language Result Execution time Memory
1060157 2024-08-15T11:05:15 Z aymanrs Nestabilnost (COI23_nestabilnost) C++17
12 / 100
 1500 ms 74744 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!=-1) 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 2 ms 1372 KB Output is correct
3 Correct 2 ms 1368 KB Output is correct
4 Correct 2 ms 1372 KB Output is correct
5 Correct 3 ms 1544 KB Output is correct
6 Correct 19 ms 1544 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 66176 KB Output is correct
2 Correct 122 ms 66132 KB Output is correct
3 Correct 114 ms 66180 KB Output is correct
4 Correct 119 ms 74744 KB Output is correct
5 Correct 119 ms 73664 KB Output is correct
6 Correct 275 ms 73848 KB Output is correct
7 Correct 1388 ms 73812 KB Output is correct
8 Execution timed out 1515 ms 73836 KB Time limit exceeded
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 1368 KB Output is correct
2 Correct 2 ms 1372 KB Output is correct
3 Correct 2 ms 1368 KB Output is correct
4 Correct 2 ms 1372 KB Output is correct
5 Correct 3 ms 1544 KB Output is correct
6 Correct 19 ms 1544 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 1368 KB Output is correct
2 Correct 2 ms 1372 KB Output is correct
3 Correct 2 ms 1368 KB Output is correct
4 Correct 2 ms 1372 KB Output is correct
5 Correct 3 ms 1544 KB Output is correct
6 Correct 19 ms 1544 KB Output is correct
7 Correct 112 ms 66176 KB Output is correct
8 Correct 122 ms 66132 KB Output is correct
9 Correct 114 ms 66180 KB Output is correct
10 Correct 119 ms 74744 KB Output is correct
11 Correct 119 ms 73664 KB Output is correct
12 Correct 275 ms 73848 KB Output is correct
13 Correct 1388 ms 73812 KB Output is correct
14 Execution timed out 1515 ms 73836 KB Time limit exceeded
15 Halted 0 ms 0 KB -