Submission #989453

#	Time	Username	Problem	Language	Result	Execution time	Memory
989453		re4ler	Sirni (COCI17_sirni)	C++14	84 / 140	1063 ms	786432 KiB

sirni

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define kienlian ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int maxn = 1e5 + 5;

struct Edge {
	int u, v, w;
};
vector<Edge> edge;
int n;
int par[maxn], sz[maxn];
int a[maxn];
int mx;
bool cmp(Edge x, Edge y) {
	return x.w < y.w;
} 
void init(int lim) {
	for(int i = 1; i <= lim; i++) {
		par[i] = i;
		sz[i] = 1;
	}
}
int find(int u) {
	if(par[u] == u) return u;
	return par[u] = find(par[u]);
}
bool unite(int u, int v) {
	int rootx = find(u);
	int rooty = find(v);
	if(rootx == rooty) return 0;
	if(sz[rootx] < sz[rooty]) swap(rootx, rooty);
	sz[rootx] += sz[rooty];
	par[rooty] = rootx;
	return 1;
}
int bs(int x, int idx) {
	int l = idx;
	int r = n;
	int res = n + 1;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(a[mid] >= x) {
			res = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	return res;
}
signed main() {
	kienlian
    cin >> n;
    set<int> st;
    for(int i = 1; i <= n; i++) {
    	int val;
    	cin >> val;
    	st.insert(val);
    	mx = max(mx, val);
    }
    int idx = 0;
    for(auto it : st) a[++idx] = it;
    n = idx;
    sort(a + 1, a + 1 + n);
	for(int i = 1; i <= n; i++) {
		int tmp = a[i];
		while(tmp <= mx) {
			int idx = bs(tmp, i + 1);
			if(idx > n) break;
			edge.push_back({idx, i, a[idx] % a[i]});
			if(tmp + a[i] <= mx) tmp += a[i];
			else break;
		}
	}
	sort(edge.begin(), edge.end(), cmp);
	init(n);
	int ans = 0;
	for(auto e : edge) {
		//cout << e.u << ' ' << e.v << ' ' << e.w << '\n';
		if(!unite(e.u, e.v)) continue;
		ans += e.w;
	}
	cout << ans;
    return 0;
}
//voi2025

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14