Submission #167373

#	Time	Username	Problem	Language	Result	Execution time	Memory
167373		sans	Sirni (COCI17_sirni)	C++14	0 / 140	1582 ms	146980 KiB

sirni

#include <iostream>
#include <numeric>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

#define sp ' '
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define forn(YY, yy) for(long long int yy = 0; yy < YY; ++yy)
#define prn(XX) cout << XX << endl
#define prs(XX) cout << XX << " "

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const int MOD = 1e9 + 7;
const int INF = 2e9 + 13;
const int mINF = -2e9 - 13;
const double PI = 3.14159265358979;
const double EPS = 1e-9;

set<pair<int, pair<int, int>>> mods;

class UnionFind{
    private:
        vector<int> p, rank, setSize;
        int numSets;
    public:
        UnionFind(int N){
            p.resize(N); rank.assign(N, 0); setSize.assign(N, 1); numSets = N;
            for(int i = 0; i < N; ++i) p[i] = i;
        }
        int findSet(int i){ return ((p[i] == i) ? i : (p[i] = findSet(p[i]))); }
        bool isSameSet(int i, int j){ return (findSet(i) == findSet(j)); }

        void unionSet(int i, int j){
            if(!isSameSet(i, j)){
                int x = findSet(i), y = findSet(j);
                numSets--;

                if(rank[x] > rank[y]){
                    p[y] = x; setSize[x] += setSize[y];
                }
                else{
                    p[x] = y; setSize[y] += setSize[x];
                    if(rank[y] == rank[x]) rank[y]++;
                }
            }
        }

        int numDisjointSet(void){ return numSets; }
        int sizeOfSet(int i){ return setSize[findSet(i)]; }
};

void maxModValue(vector<int> &arr) 
{ 
    int n = (int)arr.size();
    int ans = 0; 
    sort(arr.begin(), arr.end());
  
    for (int j = n - 2; j >= 0; --j){
        if(ans >= arr[j])  break; 
        if(arr[j] == arr[j + 1]) continue; 
  
        for (int i = 2 * arr[j]; i <= arr[n - 1] + arr[j]; i += arr[j]){
            int ind = lower_bound(arr.begin(), arr.end(), i) - arr.begin();
            mods.insert(mp(arr[ind - 1] % arr[j], mp(ind-1, j)));
        }
    }
    return;
} 

int main(int argc, char **argv){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n; cin >> n; vector<int> arr(n);
    for(auto &x: arr) cin >> x;
    maxModValue(arr);

    UnionFind UF(n);
    int minCost = 0;
    for(auto itr = mods.begin(); itr != mods.end(); ++itr){
        int u = (*itr).nd.st, v = (*itr).nd.nd;
        if(!UF.isSameSet(u, v)){
            UF.unionSet(u, v);
            minCost += (*itr).st;
        }
    }
    cout << minCost << endl;

    return 0;
}

//cikisir

• 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