Submission #863848

#	Time	Username	Problem	Language	Result	Execution time	Memory
863848		vjudge1	Sjekira (COCI20_sjekira)	C++17	110 / 110	46 ms	9600 KiB

sjekira

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int mod=1e9+7;
const int N=1e5+7;
int parent[N], h[N], a[N];
int maxi[N];
int Find(int i)
{
    if(parent[i]==i)
    {
        return i;
    }
    return parent[i]=Find(parent[i]);
}
int fm(int i)
{
    return maxi[Find(i)];
}
void unite(int i,int j)
{
    int x=Find(i),y=Find(j);
    if(x!=y)
    {
        maxi[y]=maxi[x]=max(maxi[x],maxi[y]);
        parent[y]=x;
    }
}

vector<int>v[N];
void solve()
{
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>h[i];
    }
    for(int i=0; i<n-1; i++)
    {
        int x,y;
        cin>>x>>y;
        x--,y--;
        v[x].pb(y);
        v[y].pb(x);
    }
    for(int i=0; i<n; i++)
    {
        parent[i]=i;
        maxi[i]=h[i];
    }
    for(int i=0; i<n; i++)a[i]=i;
    sort(a,a+n,[&](int i,int j)->bool
    {
        return h[i]<h[j];
    });
    for(int i=0; i<n; i++)
    {
        sort(v[i].begin(),v[i].end(),[&](int i,int j)->bool
        {
            return h[i]<h[j];
        });
    }
    int ans=0;
    bool cx[n];
    memset(cx,0,n);
    for(int i=0; i<n; i++)
    {
        cx[a[i]]=1;
        for(int j:v[a[i]])
        {
            if(cx[j])
            {
                ans+=fm(a[i])+fm(j);
                unite(a[i],j);
            }
        }
    }
    cout<<ans<<"\n";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//    freopen("paradigm,inp", "r", stdin);
//    freopen("paradigm,out", "w", stdout);
    solve();
}

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