Submission #1179347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179347		minhpk	Stove (JOI18_stove)	C++20	100 / 100	21 ms	6836 KiB

stove

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
struct node{
     int x, y, val;
};
int z[1000005];
vector <node>  v;
int sta[1000005];
int fin[1000005];
int par[1000005];
int sz[1000005];

bool cmp(node a,node b){
     return a.val<b.val;
}

int find(int u){
    if (par[u]==u){
        return u;
    }
    return par[u]=find(par[u]);
}

int tplt;
bool join(int x,int y){
    x=find(x);
    y=find(y);

    if (x==y){
        return false;
    }
    if (sz[x]<sz[y]){
        swap(x,y);
    }
    par[y]=x;
    sz[x]+=sz[y];
    sta[x]=min(sta[x],sta[y]);
    fin[x]=max(fin[x],fin[y]);
    tplt--;
    return true;
}

void krushkal(){
     for (int i=1;i<=a;i++){
         par[i]=i;
         sz[i]=1;
         sta[i]=z[i];
         fin[i]=z[i];
     }
     if (tplt==b){
        return;
     }
     for (auto p:v){
          join(p.x,p.y);
          if (tplt==b){
             break;
          }
     }
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    tplt=a;
    for (int i=1;i<=a;i++){
         cin >> z[i];
         if (i>1){
             v.push_back({i,i-1,z[i]-z[i-1]});
         }
    }
    sort(v.begin(),v.end(),cmp);
    krushkal();
    int ans=0;
    for (int i=1;i<=a;i++){
         if (par[i]==i){
           // cout << sta[i] << " " << fin[i] << " " << i << "\n";
            ans+= (fin[i]-sta[i]+1);
         }
         //cout << find(i) << "\n";
    }
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50