Submission #651176

#	Time	Username	Problem	Language	Result	Execution time	Memory
651176		Wunka	Stove (JOI18_stove)	C++17	100 / 100	60 ms	4560 KiB

stove

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

#define ll long long 
#define fi first 
#define se second 

const int INF = 1e9; 

class DSU {
public:
    vector<int> sz; 
    vector<int> id; 
    int components = 0; 
    
    void init(int n) {
        sz.assign(n, 1); 
        id.assign(n, 0); 
        for(int i = 0; i < n; i++) {
            id[i] = i; 
        }
        components = n; 
    }

    int find(int x) {
        if(x == id[x]) return x; 
        return (id[x] = find(id[x])); 
    }

    void unite(int x, int y) {
        x = find(x); 
        y = find(y); 
        if(x == y) return; 

        if(sz[x] < sz[y]) 
            swap(x, y); 
        id[y] = x; 
        sz[x] += sz[y]; 
        components--;  
    }

    int getComponents() { return components; }  
}; 

struct edge {
    int x, y, w; 
};

bool cmp(const edge& a, const edge& b) {
    return (a.w <= b.w); 
}


int main() {
    int n, k; 
    cin >> n >> k; 

    vector<ll> t(n); 
    for(int i = 0; i < n; i++) cin >> t[i]; 
    sort(t.begin(), t.end()); 
    if(n == k) {
        cout << n << '\n'; 
        return 0;  
    }

    // get our edges 
    vector<edge> e;
    for(int i = 0; i < n - 1; i++) {
        edge a; 
        a.x = i; 
        a.y = i + 1; 
        a.w = (t[i + 1] - t[i]); 
        e.push_back(a); 
    }


    // sort them 
    sort(e.begin(), e.end(), cmp); 
    /*
    cout << "my edges: " << '\n'; 
    for(int i = 0; i < n - 1; i++) {
        cout << e[i].x << ' ' << e[i].y << ' ' << e[i].w << '\n'; 
    }
    */

    // unify them into components 
    DSU uf;
    uf.init(n); 
    
   for(int i = 0; i < (n - 1) - (k - 1); i++) {
        //cout << "trying to unite " << e[i].x << ' ' << e[i].y << '\n';  
        uf.unite(e[i].x, e[i].y);
        //cout << "PASSED THIS CASE!" << '\n'; 
    }
   

    // for future 
    int m = uf.getComponents(); // number of components; 
    vector<pair<ll, ll>> intervals(n); 
    for(int i = 0; i < n; i++) {
        intervals[i].fi = INF;  
        intervals[i].se = -INF;  
    }

    for(int i = 0; i < n; i++) {
        int root = uf.find(i); 
        intervals[root].fi = min(intervals[root].fi, t[i]);  
        intervals[root].se = max(intervals[root].se, t[i] + 1);  
    }

    // calculate the answer
    ll ans = 0;
    /*
    for(int i = 0; i < n; i++) {
        cout << intervals[i].fi << ' ' << intervals[i].se << '\n'; 
    } 
    */ 
    for(int i = 0; i < n; i++) {
        if(intervals[i].fi != INF) {
            ans += intervals[i].se - intervals[i].fi; 
        }
    }

    cout << ans << '\n'; 
}

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:98:9: warning: unused variable 'm' [-Wunused-variable]
   98 |     int m = uf.getComponents(); // number of components;
      |         ^

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