oj.uz

Submission #791673

# Submission time Handle Problem Language Result Execution time Memory
791673 2023-07-24T08:45:38 Z 반딧불(#10046) Nestabilnost (COI23_nestabilnost) C++17
0 / 100
 136 ms 57636 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int arr[300002];
ll val[300002], exact[300002];

struct unionFind{
    int par[300002], mx[300002], decided[300002];

    void init(int n, int *A){
        for(int i=1; i<=n; i++){
            par[i] = i;
            mx[i] = A[i];
        }
    }

    int find(int x){
        if(x == par[x]) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y, int z){
        x = find(x), y = find(y);
        if(x==y) return;
        par[y] = x;
        mx[x] = max(mx[x], mx[y]);
        decided[x] = decided[x] | decided[y] | z;
    }

    ll getVal(int x){
        return decided[x] ? exact[decided[x]] : val[mx[x]+1];
    }
} dsu;

struct dat{
    int depth, val, x;
    dat(){}
    dat(int depth, int val, int x): depth(depth), val(val), x(x){}

    bool operator<(const dat &r)const{
        if(val!=r.val) return val>r.val;
        return depth < r.depth;
    }
};

int n;
vector<int> link[300002];
int par[300002], depth[300002];

void dfs(int x, int p = -1){
    for(auto y: link[x]){
        if(y==p) continue;
        par[y] = x, depth[y] = depth[x] + 1;
        dfs(y, x);
    }
}

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);

    vector<dat> vec;
    dsu.init(n, arr);
    for(int i=1; i<=n; i++){
        if(i!=1 && arr[i]==0) vec.push_back(dat(depth[i], arr[par[i]], i));
        else if(i!=1 && arr[par[i]] + 1 == arr[i]) dsu.merge(par[i], i, 0);
    }

    for(dat pr: vec){
        int x = pr.x, v = pr.val;
        int p = par[x], pp = dsu.find(p), px = dsu.find(x);
        if((dsu.decided[pp] && dsu.decided[pp] != v+1) || (dsu.decided[px] && dsu.decided[px] != v+1)) continue;
        if(exact[v+1] > dsu.getVal(px) + dsu.getVal(pp)) continue;
        dsu.merge(pp, px, v+1);
    }

    ll ans = 0;
    for(int i=1; i<=n; i++){
        if(dsu.find(i) != i) continue;
        ans += dsu.getVal(i);
    }
    printf("%lld", ans);
}

Compilation message

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

Subtask #1
0 / 12.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 57636 KB Output is correct
2 Incorrect 133 ms 55380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 22.0

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

Subtask #5
0 / 39.0

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