Submission #1038763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038763		Phuoc	Sirni (COCI17_sirni)	C++14	42 / 140	746 ms	786432 KiB

sirni

#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set> 

using namespace std;
 
#define ll long long
#define pb push_back
#define el '\n'
#define mpair make_pair
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define fi first
#define se second
 
/* Author: Pham Gia Phuoc */
 
const ll MOD = 998244353;
 
template <class T1, class T2>
    void add(T1 &a, T2 b){
        a += b;
        if(a >= MOD) a -= MOD;
    }
 
template <class T1, class T2>
    void sub(T1 &a, T2 b){
        a -= b;
        if(a < 0) a += MOD;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if(a > b){a = b; return true;} return false;
    }
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if(a < b){a = b; return true;} return false;
    }
 
/** END OF TEMPLATE. DRINK A CUP OF COFFEE BEFORE READING MY CODE **/
 
const int MAX = 200010;
const ll INF = (ll) 1e18 + 67LL;
const int oo = (int)(1e9 + 7);
const int NUM_BIT = 62;

#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)

int n, p[MAX];

void init(){
    cin >> n;
    FOR(i, 1, n) cin >> p[i];
}   

struct Dsu{
    int sz[MAX], par[MAX];
    Dsu(int _n = 0){
        FOR(i, 1, n){
            sz[i] = 1;
            par[i] = i;
        }
    }  

    int Find(int u){
        return u == par[u] ? u : par[u] = Find(par[u]);
    }

    bool Joint(int u, int v){
        u = Find(u); v = Find(v);
        if(u == v) return false;
        if(sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        par[v] = u;
        return true;
    }
};

struct Edge{
    int u, v, w;
    Edge(int _u = 0, int _v = 0, int _w = 0){
        u = _u; v = _v; w = _w;
    }  
};

bool cmp(Edge &song, Edge &tuyen){
    return song.w < tuyen.w;
}

namespace subtask1{
    bool check(){
        return n <= 1000;
    }   

    vector <Edge> edges;

    int solve(){
        FOR(i, 1, n) FOR(j, 1, n) if(i != j) {
            edges.push_back(Edge(i, j, min(p[i] % p[j], p[j] % p[i])));
        }
        sort(edges.begin(), edges.end(), cmp);
        long long cost = 0;
        int numEdge = 0;
        Dsu dsu(n);
        for(Edge e : edges){
            if(dsu.Joint(e.u, e.v)){
                cost += 1LL * e.w;
                numEdge++;
                if(numEdge == n - 1) break;
            }
        }
        return cost;
    }
}

int solve(){
    if(subtask1::check()) return subtask1::solve();
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define test "test"
    // freopen(test".inp", "r", stdin);
    // freopen(test".out", "w", stdout);
    srand(time(0));
    int t = 1;
    while(t--){
        init();
        cout << solve();
    }
    
    return 0;
}


 
/*** ROAD TO VOI 2025 ***/

Compilation message (stderr)

sirni.cpp: In function 'int solve()':
sirni.cpp:127:1: warning: control reaches end of non-void function [-Wreturn-type]
  127 | }
      | ^

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 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