oj.uz

답안 #1060216

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -