Submission #1154908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154908		giaminh2211	Sirni (COCI17_sirni)	C++20	140 / 140	4377 ms	527096 KiB

sirni

#include <bits/stdc++.h>

using namespace std;
using ll=long long;

const int N=1e6+13;

struct E{
	int x, y;
	ll val;

	bool operator < (const E& o){
        return val < o.val;
	}
};

struct DSU{
	int par[N];
	
	void init(int _sz){
		for(int i=0; i<=_sz; i++){
			par[i]=i;
		}
	}

	int f(int v){
		if(par[v]==v) return v;
		par[v]=f(par[v]);
		return par[v];
	}

	void uni(int u, int v){
		int Ru=f(u);
		int Rv=f(v);
		if(Ru!=Rv) par[Ru]=Rv;
	}
} dsu;

ll res=0;
int n;
ll a[N];
ll ans[N];
ll mx;
vector<E> sus;

void scan(){
    cin >> n;
    dsu.init(n+3);
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    sort(a+1, a+n+1);
    n=unique(a+1, a+n+1)-a-1;
    mx=a[n];
    //for(int i=1; i<=n; i++){
    //	cout << a[i] << ' ';
    //}
    //cout << '\n';
}

void solve(){
    for(int i=1; i<n; i++){
        for(int j=a[i]; j<=mx; j+=a[i]){
            int p=lower_bound(a+1, a+n+1, j)-a;
            if(j==a[i]) p=lower_bound(a+1, a+n+1, j+1)-a;
            if(1<=p && p<=n){
            	if(a[i] + j < a[p]) continue;
            	sus.push_back({i, p, min(a[i]%a[p], a[p]%a[i])});
            	//cerr << i << ' ' << p << ' ' << a[p]%a[i] << '\n';
            }
        }
    }
    sort(begin(sus), end(sus));
    for(auto c: sus){
    	if(dsu.f(c.x)!=dsu.f(c.y)){
    		res += c.val;
    		dsu.uni(c.x, c.y);
    	}
    }
    cout << res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    scan();
    solve();
}

• 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