Submission #852770

#	Time	Username	Problem	Language	Result	Execution time	Memory
852770		hqminhuwu	Sirni (COCI17_sirni)	C++17	140 / 140	1316 ms	769468 KiB

sirni

#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = _b; _a <= _c; ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> _c;)
#define forf(_a,_b,_c) for(_a = _b; _a < _c; ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 1e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

int par[N],sz[N];
int get (int u){
	if (u == par[u])
		return u;
	return par[u] = get(par[u]);
}
void update (int u, int v){
	if (sz[u] < sz[v])
		swap(u,v);
	par[v] = u;
	sz[u] += sz[v];
}

int n,i,a[N],f[10000002];
vector <pii> v[10000002];
ll ans;
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	forr (i,1,n)
		cin >> a[i];
	sort(a + 1, a + 1 + n);
	forr (i,1,n){
		if (a[i] != a[i + 1])
			f[a[i]] = i;
		par[i] = i;
		sz[i] = 1;
	}
	ford (i,10000000,1)
	if (!f[i])
		f[i] = f[i + 1];
	forr (i,1,n){
		if (a[i] == a[i + 1])
			continue;
		int cur = 2 * a[i];
		if (i < n)
			v[a[i + 1] % a[i]].pb({i,f[a[i + 1]]});
		while (cur <= 10000000){
			if (!f[cur])
				break;
			
			v[a[f[cur]] % a[i]].pb({i,f[cur]});
			cur += a[i];
		}
	}
	forr (i,0,10000000)
	for (pii k : v[i]){
		int p = get(k.st), q = get (k.nd);
		if (p != q)
			update(p,q), ans += i;
	}
	cout << ans << "\n";
	return 0;
}
/*



*/

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