Submission #1370323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370323		eyadooz	Sjekira (COCI20_sjekira)	C++20	110 / 110	31 ms	8764 KiB

sjekira

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define endl '\n'
#define int long long
int a[200005], cnt[200005]={}, ans=0, t=0;
bool del[200005];
vector<int> adj[200005];
void dfs(int x, int p=-1) {
    for(auto i : adj[x]) if(!del[i]) cnt[i]--;
}
main()
{
    cin.tie(0) -> sync_with_stdio(0);

    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    // a[0]=INT_MAX;
    vector<pii> b;
    int mx=0;
    for(int i = 1;i <= n;i++) {b.pb({a[i], i}); mx=max(mx, a[i]);}

    for(int i = 0;i < n-1;i++) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        cnt[u]++, cnt[v]++; 
    }

    sort(all(b));
    reverse(all(b));
    t=1;
    for(auto[w, u]:b) {
        ans+=w*(cnt[u]+1);
        del[u]=1;
        dfs(u);
        // if(cnt[u]==0) {ans+=w;continue;}
        t++;
    }
    cout << ans-mx;
    // cout << ans+b.back().first << endl;
}
    

Compilation message (stderr)

sjekira.cpp:19:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   19 | main()
      | ^~~~

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