Submission #1326654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326654		liangjeremy	Sirni (COCI17_sirni)	C++20	140 / 140	3278 ms	433984 KiB

sirni

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define fi first
#define se second
//#define int long long
using namespace std;
//using namespace __gnu_pbds;
using db=double;
using ll=int64_t;
using sll=__int128;
using lb=long double;
mt19937 rng(random_device{}()); 

struct DSU{
	vector<int>fa; vector<int>sz; 
	DSU(int n){
		fa.resize(n+1); sz.resize(n+1,1); 
		for(int i=1; i<=n; i++){ fa[i]=i; }
	}
	int find(int x){
		if(fa[x]!=x)fa[x]=find(fa[x]); 
		return fa[x]; 
	}
	void unite(int x, int y){
		int rootx=find(x); int rooty=find(y); 
		if(rootx==rooty)return; 
		if(sz[rootx]<sz[rooty])swap(rootx,rooty); 
		fa[rooty]=rootx; sz[rootx]+=sz[rooty]; 
	}
};

struct edge{
	int x; int y; int w; 
};
bool cmp(edge a, edge b){
	return a.w<b.w; 
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin>>n; vector<int>a(n); 
	for(int i=0; i<n; i++){ cin>>a[i]; }
	sort(a.begin(),a.end()); a.erase(unique(a.begin(),a.end()),a.end()); n=a.size(); int m=a.back(); vector<int>nxt(m+10,-1); 
	for(int i=0; i<n; i++){ nxt[a[i]]=i; }
	for(int i=m; i>=1; i--){
		if(nxt[i]==-1)nxt[i]=nxt[i+1]; 
	}
	vector<edge>v; 
	for(int i=0; i<n; i++){
		int idx=nxt[a[i]+1]; 
		if(idx!=-1 && a[idx]<2*a[i])v.push_back({i,idx,a[idx]%a[i]}); 
		for(int j=2*a[i]; j<=m; j+=a[i]){
			int idx=nxt[j]; 
			if(idx!=-1 && a[idx]<j+a[i])v.push_back({i,idx,a[idx]%a[i]}); 
		}
	}
	DSU dsu(n+100); sort(v.begin(),v.end(),cmp); ll ans=0; 
	for(auto cur:v){
		if(dsu.find(cur.x)!=dsu.find(cur.y)){
			ans+=cur.w; dsu.unite(cur.x,cur.y);
		}
	}
	cout<<ans<<"\n"; 
	//对于 [a[i]*k,a[i]*k+a[i]-1]这个区间内的所有数，除了其中最小的数，和区间内其他的数连边都是无意义的
}
/*
山雀 - 万能青年旅店
 
自然赠予你 树冠 微风 肩头的暴雨
片刻后生成 平衡 忠诚 不息的身体
捕食饮水 清早眉间白云生
跳跃漫游 晚来拂面渤海风
 
朝霞化精灵 轻快 明亮 恒温的伴侣
她与你共存 违背 对抗 相同的命运
爱与疼痛 不觉茫茫道路长
生活历险 并肩莽莽原野荒
 
山崖复远望 仓皇 无告 不回的河流
平原不可见 晦暗 无声 未知的存亡
大雾重重 时代喧哗造物忙
火光忷忷 指引盗寇入太行
 
大雾重重 时代喧哗造物忙
火光忷忷 指引盗寇入太行
*/

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14