제출 #1139165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139165		ChottuF	Sirni (COCI17_sirni)	C++20	0 / 140	348 ms	7048 KiB

sirni

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

struct DSU{
    vector<int> parent,sz;
    DSU(int n){
        parent.resize(n);
        sz.resize(n,1);
        for (int i = 0; i<n; i++){
            parent[i] = i;;
        }
    }
    
    int find(int x){
        if (x != parent[x]){
            return parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    bool merge(int a, int b){
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (sz[b] > sz[a]) swap(a,b);
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

int func(int x, int y){
    int zz = x/y; zz *= y;
    return zz;
}

int main(){
    int n;
    cin >> n;
    int arr[n];
    map<int,int> mp;
    for (int i = 0; i<n; i++){
        cin >> arr[i];
        mp[arr[i]] = i;
    }
    sort(arr,arr+n);
    priority_queue<pair<int,int>> pq;
    int mx = arr[n-1];
    for (int i = 0; i<n; i++){
        pq.push({func(mx,arr[i]),arr[i]});
    }
    int i = n-1;
    int ans = 0;
    DSU dsu(n);
    while (!pq.empty() && i >= 0){
        auto [a,b] = pq.top();
        if (a > arr[i]){
            pq.pop();
            pq.push({func(arr[i],b),b});
        }
        else if (b == a){
            pq.pop();
        }
        else{
            if (dsu.merge(i, mp[b])){
                ans += arr[i] - a;
                i--;
            }
            else{
                pq.pop();
            }
        }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14