/**
* 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();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
39636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
39700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
30016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
10580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
457 ms |
103908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
13904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
285 ms |
89924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
342 ms |
90152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
45868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
