Submission #767711

#	Time	Username	Problem	Language	Result	Execution time	Memory
767711		Pichon5	Sjekira (COCI20_sjekira)	C++17	110 / 110	47 ms	7024 KiB

sjekira

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <sstream>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define int long long
using namespace std;
const int tam=100005;
int v[tam];

bool cmp(pair<int,int> a,pair<int,int> b){
    return max(v[a.F],v[a.S])<max(v[b.F],v[b.S]);
}
int P[tam];
int majo[tam];
int _find(int x){
    if(P[x]==x)return x;
    return P[x]=_find(P[x]);
}
int res=0;
int _union(int a, int b){
    a=_find(a);b=_find(b);
    P[a]=b;
    int devuelvo=majo[a]+majo[b];
    majo[b]=max(majo[a],majo[b]);
    return devuelvo;
}

signed main(){
    fast
    int n,x,a,b;
    cin>>n;
    int res=0;
    vector<pair<int,int>>E;
    for(int i=1;i<=n;i++){
        P[i]=i;
        cin>>v[i];
        majo[i]=v[i];
    }
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        E.pb({a,b});
    }
    sort(E.begin(),E.end(),cmp);
    for(int i=0;i<E.size();i++){
        int a=E[i].F,b=E[i].S;
        int val=_union(a,b);
        // cout<<"val "<<val<<endl;
        res+=val;
    }
    cout<<res<<endl;
    return 0;
}

Compilation message (stderr)

sjekira.cpp: In function 'int main()':
sjekira.cpp:62:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<E.size();i++){
      |                 ~^~~~~~~~~
sjekira.cpp:48:11: warning: unused variable 'x' [-Wunused-variable]
   48 |     int n,x,a,b;
      |           ^

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