oj.uz

Submission #468706

# Submission time Handle Problem Language Result Execution time Memory
468706 2021-08-29T12:34:01 Z Autron Sirni (COCI17_sirni) C++14
140 / 140
 3863 ms 708308 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> p;
vector<pair<int, int>> e[10000002];
vector<int> fat, sz;

int get(int x){
	if(fat[x]==x) return x;
	return fat[x]=get(fat[x]);
}

int sol=0;
void join(int a, int b, int c){
	a=get(a), b=get(b);
	if(a==b) return;
	sol+=c;
	if(sz[a]<sz[b]) swap(a, b);
	sz[a]+=sz[b];
	fat[b]=a;
}

int main(){
	cin>>n;
	p.resize(n+1), fat.resize(n+1), sz.resize(n+1);
	for(int i=1;i<=n;++i) cin>>p[i], fat[i]=i, sz[i]=1;
	sort(p.begin()+1, p.end());
	p.resize(unique(p.begin(), p.end())-p.begin());
	n=p.size()-1;
	int m=p[n];
	for(int i=1;i<=n;++i){
		int j=i+1;
		for(int x=p[i];x<=m;x+=p[i]){
			while(j<=n&&p[j]<x) j++;
			if(j<=n) e[p[j]%p[i]].push_back({i, j});
		}
	}
	for(int i=0;i<=m;++i){
		for(auto it:e[i]) join(it.first, it.second, i);
	}
	cout<<sol<<"\n";
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 235216 KB Output is correct
2 Correct 226 ms 264744 KB Output is correct
3 Correct 147 ms 235524 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 235216 KB Output is correct
2 Correct 1412 ms 630032 KB Output is correct
3 Correct 159 ms 235964 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 235428 KB Output is correct
2 Correct 158 ms 235076 KB Output is correct
3 Correct 153 ms 235292 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1623 ms 246492 KB Output is correct
2 Correct 1584 ms 274692 KB Output is correct
3 Correct 1201 ms 257440 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 237248 KB Output is correct
2 Correct 282 ms 259440 KB Output is correct
3 Correct 1189 ms 246460 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1733 ms 258688 KB Output is correct
2 Correct 1835 ms 292104 KB Output is correct
3 Correct 1617 ms 255632 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 239148 KB Output is correct
2 Correct 1659 ms 292968 KB Output is correct
3 Correct 1339 ms 257440 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1776 ms 250008 KB Output is correct
2 Correct 3088 ms 594984 KB Output is correct
3 Correct 1810 ms 252752 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1809 ms 254352 KB Output is correct
2 Correct 3863 ms 708308 KB Output is correct
3 Correct 1992 ms 310152 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 237748 KB Output is correct
2 Correct 3285 ms 596268 KB Output is correct
3 Correct 1411 ms 259500 KB Output is correct