oj.uz

Submission #854849

# Submission time Handle Problem Language Result Execution time Memory
854849 2023-09-29T06:24:16 Z noyancanturk Sjekira (COCI20_sjekira) C++17
50 / 110
 1000 ms 33980 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define lim 100005
using namespace std;
const int mod=1000000007ll;

int parent[lim];
int maxi[lim];
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;
    }
}

unordered_set<int>v[lim];
void solve(){
    int n;
    cin>>n;
    int h[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].insert(y);
        v[y].insert(x);
    }
    for(int i=0;i<n;i++){
        parent[i]=i;
        maxi[i]=h[i];
    }
    set<array<int,3>>all;
    for(int i=0;i<n;i++){
        for(int j:v[i]){
            all.insert({max(fm(j),fm(i)),min(i,j),max(i,j)});
        }
    }
    int ans=0;
    while(all.size()){
        //cerr<<all.size()<<"\n";
        /*
        for(auto p:all){
            cerr<<p[0]<<" "<<p[1]+1<<" "<<p[2]+1<<"\n";
        }cerr<<"\n";
        */
        auto p=*all.begin();
        all.erase(p);
        //cerr<<all.size()<<"\n";
        v[p[2]].erase(p[1]);
        v[p[1]].erase(p[2]);
        if(fm(p[1])>fm(p[2])){
            swap(p[2],p[1]);
        }
        ans+=fm(p[1])+fm(p[2]);
        for(int i:v[p[1]]){
            if(!all.empty()&&all.count({max(fm(p[1]),fm(i)),min(p[1],i),max(p[1],i)})){
                //cerr<<all.size()<<"hmm1\n";
                all.erase({max(fm(p[1]),fm(i)),min(p[1],i),max(p[1],i)});
                //cerr<<all.size()<<"hmm2\n";
                all.insert({max(fm(p[2]),fm(i)),min(p[1],i),max(p[1],i)});
            }
        }
        unite(p[1],p[2]);
    }
    cout<<ans<<"\n";
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6784 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 27204 KB Output is correct
2 Correct 89 ms 23488 KB Output is correct
3 Correct 74 ms 22920 KB Output is correct
4 Correct 86 ms 24660 KB Output is correct
5 Correct 158 ms 33980 KB Output is correct
6 Correct 90 ms 33616 KB Output is correct
7 Correct 72 ms 30144 KB Output is correct
8 Correct 65 ms 27952 KB Output is correct
9 Correct 47 ms 20596 KB Output is correct
10 Correct 85 ms 33860 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6784 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 3 ms 7004 KB Output is correct
7 Correct 3 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 3 ms 7004 KB Output is correct
10 Correct 3 ms 7004 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6784 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 120 ms 27204 KB Output is correct
7 Correct 89 ms 23488 KB Output is correct
8 Correct 74 ms 22920 KB Output is correct
9 Correct 86 ms 24660 KB Output is correct
10 Correct 158 ms 33980 KB Output is correct
11 Correct 90 ms 33616 KB Output is correct
12 Correct 72 ms 30144 KB Output is correct
13 Correct 65 ms 27952 KB Output is correct
14 Correct 47 ms 20596 KB Output is correct
15 Correct 85 ms 33860 KB Output is correct
16 Correct 3 ms 7004 KB Output is correct
17 Correct 3 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 3 ms 7004 KB Output is correct
20 Correct 3 ms 7004 KB Output is correct
21 Correct 36 ms 12880 KB Output is correct
22 Correct 29 ms 11868 KB Output is correct
23 Correct 234 ms 32496 KB Output is correct
24 Correct 130 ms 24912 KB Output is correct
25 Correct 127 ms 24836 KB Output is correct
26 Correct 85 ms 18792 KB Output is correct
27 Correct 108 ms 20880 KB Output is correct
28 Execution timed out 1027 ms 25992 KB Time limit exceeded
29 Halted 0 ms 0 KB -