oj.uz

답안 #852770

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
852770 2023-09-22T16:37:41 Z hqminhuwu Sirni (COCI17_sirni) C++17
140 / 140
 1316 ms 769468 KB 
#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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 275740 KB Output is correct
2 Correct 150 ms 304976 KB Output is correct
3 Correct 101 ms 275792 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 275536 KB Output is correct
2 Correct 735 ms 685720 KB Output is correct
3 Correct 102 ms 276308 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 275600 KB Output is correct
2 Correct 102 ms 275536 KB Output is correct
3 Correct 104 ms 275592 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 286044 KB Output is correct
2 Correct 190 ms 316660 KB Output is correct
3 Correct 156 ms 299036 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 277604 KB Output is correct
2 Correct 162 ms 298928 KB Output is correct
3 Correct 146 ms 285764 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 297820 KB Output is correct
2 Correct 213 ms 336496 KB Output is correct
3 Correct 154 ms 294912 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 279028 KB Output is correct
2 Correct 219 ms 333600 KB Output is correct
3 Correct 154 ms 300088 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 289092 KB Output is correct
2 Correct 803 ms 652748 KB Output is correct
3 Correct 158 ms 291932 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 293604 KB Output is correct
2 Correct 1316 ms 769468 KB Output is correct
3 Correct 246 ms 350448 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 277840 KB Output is correct
2 Correct 1259 ms 635648 KB Output is correct
3 Correct 157 ms 299584 KB Output is correct