oj.uz

Submission #791839

# Submission time Handle Problem Language Result Execution time Memory
791839 2023-07-24T10:50:47 Z 반딧불(#10046) Nestabilnost (COI23_nestabilnost) C++17
32 / 100
 285 ms 95292 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

int n;
vector<int> link[300002];
int arr[300002];
ll val[300002], exact[300002];

struct Result{
    map<int, ll> mp[2];
    Result(){}

    void swap(Result &nxt){
        mp[0].swap(nxt.mp[0]);
        mp[1].swap(nxt.mp[1]);
    }

    void clearUp(int x, int y){
        if(arr[x] + 1 == arr[y]){ /// mp[0], mp[1] ��� ���ӵ� �� �ִ� ���
            int zv = arr[x] + 1;
            ll minV = INF, minZV = INF;
            map<int, ll>::iterator it = mp[0].begin();
            while(it != mp[0].end()){
                if(it->first > zv) break;
                minV = min(minV, it->second + val[it->first]);
                minZV = min(minZV, it->second);
                ++it;
                mp[0].erase(prev(it));
            }
            it = mp[1].begin();
            while(it != mp[1].end()){
                if(it->first > zv) break;
                minV = min(minV, it->second + exact[it->first]);
                ++it;
                mp[1].erase(prev(it));
            }
            mp[0][0] = minV;
            if(minZV != INF) mp[1][zv] = minZV;
        }
        else if(arr[y] == 0){ /// mp[0]�� ��� �������, mp[1]�� �Ϻ� ���� ������ ���
            int ov = arr[x] + 1;
            ll minV = INF, minOV = INF;
            for(pair<int, ll> p: mp[0]){
                minV = min(minV, p.second + val[p.first]);
                if(p.first <= ov) minOV = min(minOV, p.second);
            }
            for(pair<int, ll> p: mp[1]){
                minV = min(minV, p.second + exact[p.first]);
                if(p.first == ov) minOV = min(minOV, p.second);
            }
            mp[0].clear(), mp[1].clear();
            mp[0][0] = minV;
            if(minOV != INF) mp[1][ov] = minOV;
        }
        else{ /// � ���൵ �Ұ����� ���
            ll minV = INF;
            for(pair<int, ll> p: mp[0]) minV = min(minV, p.second + val[p.first]);
            for(pair<int, ll> p: mp[1]) minV = min(minV, p.second + exact[p.first]);
            mp[0].clear(), mp[1].clear();
            mp[0][0] = minV;
        }
    }

    void makeUp(int v){
        mp[0][v+1] = mp[0][0];
        mp[0].erase(0);
    }
} DP[300002];

void dfs(int x, int p=-1){
    if(p!=-1) link[x].erase(find(link[x].begin(), link[x].end(), p));
    if(link[x].empty()){
        DP[x].mp[0][0] = val[arr[x]+1];
        DP[x].mp[0][arr[x]+1] = 0;
        return;
    }
    int y = link[x][0];
    dfs(y, x);

    DP[x].swap(DP[y]);
    DP[x].clearUp(x, y);
    DP[x].makeUp(arr[x]);

//    printf("DP[%d]\n", x);
//    for(int d=0; d<2; d++){
//        printf("mp[%d]: ", d);
//        for(pair<int, ll> p: DP[x].mp[d]) printf("(%d, %lld) ", p.first, p.second);
//        puts("");
//    }
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
    for(int i=1; i<=n; i++) scanf("%lld", &exact[i]), val[i] = exact[i];
    for(int i=n-1; i>=1; i--) val[i] = min(val[i+1], val[i]);
    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        link[y].push_back(x);
    }

    dfs(1);

    ll ans = INF;
    for(pair<int, ll> p: DP[1].mp[0]) ans = min(ans, p.second + val[p.first]);
    for(pair<int, ll> p: DP[1].mp[1]) ans = min(ans, p.second + exact[p.first]);
    printf("%lld", ans);

    return 0;
}

Compilation message

code1.cpp: In function 'int main()':
code1.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
code1.cpp:98:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
code1.cpp:99:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     for(int i=1; i<=n; i++) scanf("%lld", &exact[i]), val[i] = exact[i];
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~
code1.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 36308 KB Output is correct
2 Correct 27 ms 36340 KB Output is correct
3 Correct 21 ms 36348 KB Output is correct
4 Correct 21 ms 36264 KB Output is correct
5 Correct 22 ms 36316 KB Output is correct
6 Correct 21 ms 36268 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 83896 KB Output is correct
2 Correct 193 ms 83768 KB Output is correct
3 Correct 204 ms 84120 KB Output is correct
4 Correct 285 ms 95292 KB Output is correct
5 Correct 204 ms 84184 KB Output is correct
6 Correct 193 ms 84148 KB Output is correct
7 Correct 190 ms 84088 KB Output is correct
8 Correct 194 ms 84128 KB Output is correct
9 Correct 195 ms 84124 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 36308 KB Output is correct
2 Correct 27 ms 36340 KB Output is correct
3 Correct 21 ms 36348 KB Output is correct
4 Correct 21 ms 36264 KB Output is correct
5 Correct 22 ms 36316 KB Output is correct
6 Correct 21 ms 36268 KB Output is correct
7 Incorrect 19 ms 35540 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 36308 KB Output is correct
2 Correct 27 ms 36340 KB Output is correct
3 Correct 21 ms 36348 KB Output is correct
4 Correct 21 ms 36264 KB Output is correct
5 Correct 22 ms 36316 KB Output is correct
6 Correct 21 ms 36268 KB Output is correct
7 Correct 198 ms 83896 KB Output is correct
8 Correct 193 ms 83768 KB Output is correct
9 Correct 204 ms 84120 KB Output is correct
10 Correct 285 ms 95292 KB Output is correct
11 Correct 204 ms 84184 KB Output is correct
12 Correct 193 ms 84148 KB Output is correct
13 Correct 190 ms 84088 KB Output is correct
14 Correct 194 ms 84128 KB Output is correct
15 Correct 195 ms 84124 KB Output is correct
16 Incorrect 19 ms 35540 KB Output isn't correct
17 Halted 0 ms 0 KB -