제출 #639862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
639862		quangphat18ti	Sirni (COCI17_sirni)	C++14	0 / 140	452 ms	103184 KiB

sirni

/**
 * 5h07: 84%
 * Link: https://oj.uz/problem/view/COCI17_sirni
 * 
 * Đề:
 * Cho mảng A có N phần tử.
 * Trọng số mỗi cặp A[i] và A[j] là: min(A[i]%A[j], A[j]%A[i])
 * Tìm cây khung nhỏ nhất liên kết N thằng với chi phí là min nhất.
*/

/**
 * Vấn đề đặt ra: Số đỉnh quá lớn để có thể build cạnh và DSU
 * 
 * Nhận xét 1: 
 *      + Và như vậy, các đỉnh có giá trị bằng nhau thì mình sẽ không cần xét đến nó.
 *      + Như vậy, ta sẽ chuyển bài toán về thành các giá trị khác nhau
 * 
 * Nhận xét 2:
 *      + Dễ dàng nhận thấy, vì max_val = 1e7 nên ta có thể dễ dàng lặp qua các bội số của các giá trị trong mảng A
 *      + Và ta sẽ kết nối các giá trị này lại với trọng số cạnh = 0
 * 
 * Nhận xét 3:
 *      + Giả sử A[i] > A[j] thì trọng số là A[i] % A[j]
 *      + Ta có thể dễ dàng tính bằng cách duyệt qua các bội số của A[j]
 * 
 * Nhận xét 4:
 *      + Vì ta không biết từ 1 bội số, hay 1 giá trị thì ta cần nối tới bao nhiêu cạnh
 *         gần nhất.
 *      + Nên ta sẽ tìm kiếm nhị phân giá trị cạnh lớn nhất để DSU 
 *      + Hoặc tìm kiếm nhị phân số cạnh cần nối từ 1 đỉnh đi ra để hoàn chỉnh cây DSU
 * 
 * Nhận xét 5: 
 *      + .... 
 *      + Ta dễ dàng chứng minh chỉ cần xét 1 đỉnh gần nhất.
*/

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

#define all(_x) _x.begin(), _x.end()
#define fi first
#define se second
#define sz(_s) int(_s.size())
#define mp make_pair
#define trav(a, x) for(auto& a: x)

#define fu(i, a, b) for(int i = a; i <= b; ++i)
#define fd(i, a, b) for(int i = a; i >= b; --i)
#define fr(i, n) for(int i = 0; i < n; ++i)

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;

template<class T>
ostream& operator << (ostream& out, vector<T> &a) {
    trav(x, a) cout << x << ' ';
    return out;
}

class Edge{
public:
    int u, v, w;

    bool operator < (const Edge &A) {
        return w < A.w;
    }
};


struct DSU{
    // par[u] là đỉnh đại diện cho u
    vector<int> par;
    
    // reset mảng cho n phần tử
    void init(int n){ 
        par.assign(n, -1);
    }

    // lấy ra đỉnh đại diện cho nhánh chứa x
    int get(int x) {
        return par[x] < 0 ? x : par[x] = get(par[x]);
    }

    // kiểm tra x và y có chung 1 nhánh hay không
    bool sameSet(int x, int y) {
        return get(x) == get(y);
    }

    // số phần tử nhánh liên thông của x
    int size(int x) {
        return -par[get(x)];
    }

    // Nối cạnh x y
    bool unite(int x, int y) {
        int u = get(x);
        int v = get(y);
        if(u == v) return false;

        if(par[u] > par[v]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
        return true;
    }
};


vector<Edge> edges;

int n, max_val;
vector<int> a;
vector<int> pos;


void initData(){
    cin >> n;
    a.resize(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    
    sort(all(a));
    a.erase(unique(all(a)), a.end());
    max_val = *max_element(all(a));
    n = a.size();

    pos.assign(max_val + 1, 0);
    for(int i = 0; i < n; ++i) pos[a[i]] = i;
}

int calc(int x, int y) {
    if(x > y) swap(x, y);
    return a[y] % a[x]; 
}

void build_edge() {
    for(int i = 0; i < n; ++i) {
        int u = a[i];
        for(int v = u * 2; v <= max_val; v += u) {
            int j = pos[v];
            edges.push_back({i, j, 0});

            int k = upper_bound(all(a), v) - a.begin();
            if(k >= n) continue;

            edges.push_back({i, k, calc(i, k)});
        }
    }
}

void solve() {
    sort(all(edges));
    DSU dsu;
    dsu.init(n);

    ll ans = 0;
    trav(e, edges) {
        if(dsu.unite(e.u, e.v)) ans += e.w;
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    
    int t = 1; 
    //cin >> t;
    while(t--) {
        initData();
        build_edge();
        solve();
    }
}

• 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