제출 #1140903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140903		madamadam3	Sirni (COCI17_sirni)	C++17	42 / 140	80 ms	12716 KiB

sirni

#include <bits/stdc++.h>

using namespace std;

// typedefs
// #define int long long int
typedef long long ll;
typedef long double ld;
using str = string;
// typedef double ld;

// pairs
template <class T> using P = pair<T, T>;
using pi = P<int>;
using pl = P<ll>;
using pd = P<ld>;
using weg = pair<int, pi>; // weighted edge

#define mp make_pair
#define f first
#define s second

// vectors
template <class T> using V = vector<T>;
using vi = V<int>;
using vl = V<ll>;
using vd = V<ld>;
using vb = V<bool>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;
using vvi = V<vi>;
using vweg = V<weg>;

#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))
#define pb push_back

#define lb lower_bound
#define ub upper_bound
template<class T> int ilb(V<T>& a, const T& b) {return int(lb(all(a), b) - (a).begin());}
template<class T> int iub(V<T>& a, const T& b) {return int(ub(all(a), b) - (a).begin());}

// queues
template<class T> using prq = priority_queue<T, V<T>>;

// macros
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (a); i >= (b); --i)
#define rep(a) FOR (_, 0, a) 
#define each(a, x) for (auto& a: x)
#define trace(x) each(a, (x)) {cout << a << " ";}
#define tracel(x) each(a, (x)) {cout << a << "\n";}

vi parent;

int fs(int v) {
    if (v == parent[v]) {
        return v;
    }
    return parent[v] = fs(parent[v]);
}

void solve() {
    int n;
    cin >> n;

    vi p(n); FOR(i, 0, n) {cin >> p[i];}

    set<int> ts(all(p)); // ts ??
    p.assign(all(ts));
    n = p.size();

    if (n > 1000) {
        return;
    }

    parent.resize(n);
    iota(all(parent), 0);

    vweg edges;
    FOR(i, 0, n) {
        FOR(j, 0, n) {
            edges.pb(mp(p[i] % p[j], mp(i, j)));
        }
    }

    srt(edges);

    int cost = 0;

    each(edge, edges) {
        int ec = edge.f;
        int u = edge.s.f;
        int v = edge.s.s;

        u = fs(u);
        v = fs(v);

        if (u != v) {
            parent[v] = u;
            cost += ec;
        }
    }

    cout << cost << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    solve();
}

• 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