oj.uz

Submission #989453

# Submission time Handle Problem Language Result Execution time Memory
989453 2024-05-28T07:59:32 Z re4ler Sirni (COCI17_sirni) C++14
84 / 140
 1063 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;
    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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2716 KB Output is correct
2 Correct 310 ms 98980 KB Output is correct
3 Correct 4 ms 3028 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 648 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 2840 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 3 ms 2880 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 57008 KB Output is correct
2 Correct 798 ms 105868 KB Output is correct
3 Correct 370 ms 105520 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8648 KB Output is correct
2 Correct 384 ms 100068 KB Output is correct
3 Correct 207 ms 58028 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 106384 KB Output is correct
2 Correct 1004 ms 204600 KB Output is correct
3 Correct 310 ms 56996 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 17352 KB Output is correct
2 Correct 1063 ms 203824 KB Output is correct
3 Correct 316 ms 56472 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 57744 KB Output is correct
2 Runtime error 762 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 318 ms 57500 KB Output is correct
2 Runtime error 747 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 37 ms 8904 KB Output is correct
2 Runtime error 1018 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -