Submission #639975

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
639975	2022-09-13T04:21:31 Z	quangphat18ti	Sirni (COCI17_sirni)	C++14	84 / 140	2316 ms	786432 KB

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ấ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;

void initData(){
    cin >> n;
    a.resize(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    
    sort(all(a));
    a.resize(unique(all(a)) - a.begin());
    max_val = a.back();
    n = a.size();
}

void build_edge() {
    // cout << n << ' ' << max_val << endl;
    for(int i = 0; i < n - 1; ++i) {
        edges.push_back({i, i + 1, a[i+1] - a[i]});
        for(int j = a[i]*2; j <= max_val; j += a[i]) {
            int k = lower_bound(a.begin(), a.end(), j) - a.begin();
            if(k >= n) continue;
            edges.push_back({i, k, a[k] - j});
        }
    }
}

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
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	262 ms	49632 KB	Output is correct
3	Correct	4 ms	788 KB	Output is correct

Subtask #2
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Runtime error	1014 ms	786432 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #3
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	2 ms	596 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	156 ms	25452 KB	Output is correct
2	Correct	532 ms	50852 KB	Output is correct
3	Correct	260 ms	50836 KB	Output is correct

Subtask #5
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	3528 KB	Output is correct
2	Correct	285 ms	50544 KB	Output is correct
3	Correct	149 ms	26016 KB	Output is correct

Subtask #6
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	331 ms	50080 KB	Output is correct
2	Correct	736 ms	99964 KB	Output is correct
3	Correct	225 ms	26068 KB	Output is correct

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	6784 KB	Output is correct
2	Correct	752 ms	99832 KB	Output is correct
3	Correct	232 ms	26084 KB	Output is correct

Subtask #8
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	194 ms	25376 KB	Output is correct
2	Runtime error	1792 ms	786432 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #9
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	239 ms	25356 KB	Output is correct
2	Runtime error	1648 ms	786432 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	3528 KB	Output is correct
2	Runtime error	2316 ms	786432 KB	Execution killed with signal 9
3	Halted	0 ms	0 KB	-

Submission #639975

Compilation message