oj.uz

Submission #989504

# Submission time Handle Problem Language Result Execution time Memory
989504 2024-05-28T08:38:30 Z re4ler Sirni (COCI17_sirni) C++17
84 / 140
 1272 ms 786432 KB 
#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;
    bool ok = 1;
    for(int i = 1; i <= n; i++) {
    	int val;
    	cin >> val;
    	st.insert(val);
    	mx = max(mx, val);
    	if(val == 1) ok = 0;
    }
    if(!ok) {
    	cout << 0;
    	return 0;
    }
    int idx = 0;
    for(auto it : st) a[++idx] = it;
    if(idx == 1) {
    	cout << 0;
    	return 0;
    }
    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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2716 KB Output is correct
2 Correct 354 ms 98968 KB Output is correct
3 Correct 4 ms 1368 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2844 KB Output is correct
2 Runtime error 680 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 2 ms 2844 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2904 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 57024 KB Output is correct
2 Correct 801 ms 106016 KB Output is correct
3 Correct 411 ms 105572 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9164 KB Output is correct
2 Correct 405 ms 99944 KB Output is correct
3 Correct 233 ms 56216 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 106332 KB Output is correct
2 Correct 1106 ms 204544 KB Output is correct
3 Correct 346 ms 56976 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16832 KB Output is correct
2 Correct 1064 ms 203668 KB Output is correct
3 Correct 330 ms 56472 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 57492 KB Output is correct
2 Runtime error 919 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 344 ms 57332 KB Output is correct
2 Runtime error 883 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 40 ms 9420 KB Output is correct
2 Runtime error 1272 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -