Submission #328087

#	Time	Username	Problem	Language	Result	Execution time	Memory
328087		model_code	Sjekira (COCI20_sjekira)	C++17	110 / 110	64 ms	3936 KiB

sjekira

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 100005;

typedef pair<int,int> ii;

int n;
int t[MAXN];
vector<ii> e;
int uf[MAXN], mv[MAXN];

bool cmp(const ii& a, const ii& b) {
    int x = max(t[a.first], t[a.second]);
    int y = max(t[b.first], t[b.second]);
    return x<y;
}
int fnd(int x){
    if(x==uf[x]) return x;
    else return uf[x]=fnd(uf[x]);
}

long long sol = 0;

void un(int x, int y){
    x = fnd(x);
    y = fnd(y);
    if(x != y){
        sol += mv[x] + mv[y];
        mv[y] = max(mv[y], mv[x]);    
        uf[x] = y;
    }
}

int main(){
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%d", &t[i]);
        uf[i] = i;
        mv[i] = t[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d", &u, &v);
        e.push_back(ii(u-1, v-1));
    }
    sort(e.begin(), e.end(), cmp);
    for(auto i:e){
        un(i.first, i.second);
    }
    printf("%lld\n", sol);
}

Compilation message (stderr)

sjekira.cpp: In function 'int main()':
sjekira.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
sjekira.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         scanf("%d", &t[i]);
      |         ~~~~~^~~~~~~~~~~~~
sjekira.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60