oj.uz

Submission #436836

# Submission time Handle Problem Language Result Execution time Memory
436836 2021-06-25T03:23:02 Z penguinhacker Sirni (COCI17_sirni) C++14
140 / 140
 2932 ms 612280 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5, mxP=1e7; // change to 1e7
int n, nxt[mxP+1], ind[mxP+1], n2, p[mxN];
vector<ar<int, 2>> e[mxP];

int find(int i) {
	return i^p[i]?p[i]=find(p[i]):i;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	cin >> n;
	//n=100000;
	for (int i=0; i<n; ++i) {
		int x;
		cin >> x;
		//x=rng()%9999000+1000;
		nxt[x]=x;
	}
	for (int i=1; i<=mxP; ++i)
		if (nxt[i])
			ind[i]=n2++;
	for (int i=mxP-1; i; --i)
		if (!nxt[i])
			nxt[i]=nxt[i+1];
	if (nxt[1]==1) {
		cout << 0;
		return 0;
	}
	for (int i=2; i<mxP; ++i) {
		if (i^nxt[i])
			continue;
		if (nxt[i+1]<2*i&&nxt[i+1])
			e[nxt[i+1]-i].push_back({ind[i], ind[nxt[i+1]]});
		for (int j=2*i; j<=mxP&&nxt[j]; j+=i)
			if (nxt[j]<j+i)
				e[nxt[j]-j].push_back({ind[i], ind[nxt[j]]});
	}
	//sort(e.begin(), e.end());
	iota(p, p+n2, 0);
	int ans=0, cmp=n2;
	for (int i=0; i<mxP; ++i)
		for (ar<int, 2> a : e[i]) {
			int u=find(a[0]), v=find(a[1]);
			if (u^v) {
				p[v]=u;
				--cmp;
				ans+=i;
			}
		}
	assert(cmp==1);
	cout << ans;
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 278104 KB Output is correct
2 Correct 334 ms 278784 KB Output is correct
3 Correct 254 ms 278340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 274516 KB Output is correct
2 Correct 598 ms 275472 KB Output is correct
3 Correct 259 ms 278336 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 278388 KB Output is correct
2 Correct 264 ms 276680 KB Output is correct
3 Correct 256 ms 278428 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 288324 KB Output is correct
2 Correct 463 ms 315600 KB Output is correct
3 Correct 353 ms 293736 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 280048 KB Output is correct
2 Correct 362 ms 299760 KB Output is correct
3 Correct 293 ms 286772 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 300648 KB Output is correct
2 Correct 562 ms 330160 KB Output is correct
3 Correct 345 ms 292048 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 278564 KB Output is correct
2 Correct 478 ms 324916 KB Output is correct
3 Correct 380 ms 291692 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 326512 KB Output is correct
2 Correct 2005 ms 522780 KB Output is correct
3 Correct 437 ms 328944 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 326388 KB Output is correct
2 Correct 2932 ms 612280 KB Output is correct
3 Correct 578 ms 332656 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 310880 KB Output is correct
2 Correct 2640 ms 600620 KB Output is correct
3 Correct 343 ms 293564 KB Output is correct