Submission #1303965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303965		yus1f_m	Sirni (COCI17_sirni)	C++20	42 / 140	5093 ms	6656 KiB

sirni

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define str string
#define pb push_back
#define pf push_front
#define in insert
#define all(v) v.begin(),v.end()
const int sz=100001,INF=1000000000;
using namespace std;
vector<ll>parent(sz,-1);
ll get(ll num)
{
    if(parent[num]<0)
    {
        return num;
    }
    else
    {
        parent[num]=get(parent[num]);
        return get(parent[num]);
    }
}
void unite(ll num1,ll num2)
{
    ll res1=get(num1),res2=get(num2);
    if(res1!=res2)
    {
        if(parent[res1]>parent[res2])
        {
            swap(res1,res2);
        }
        parent[res1]+=parent[res2],parent[res2]=res1;
    }
}
void solve()
{
    ll n,num,num1,num2,Res,ans=0;
    cin>>n;
    vector<ll>nums;
    set<ll>res;
    for(int i=0;i<n;i++)
    {
        cin>>num;
        nums.pb(num);
    }
    while(true)
    {
        for(int i=1;i<=n;i++)
        {
            res.in(get(i));
        }
        if(res.size()==1)
        {
            break;
        }
        else
        {
            res.clear(),Res=INF;
            for(int i=0;i<nums.size();i++)
            {
                for(int j=i+1;j<nums.size();j++)
                {
                    if(get(i+1)!=get(j+1))
                    {
                        if(Res>min(nums[i]%nums[j],nums[j]%nums[i]))
                        {
                            Res=min(nums[i]%nums[j],nums[j]%nums[i]),num1=i+1,num2=j+1;
                        }
                    }
                }
            }
            ans+=Res,unite(num1,num2);
        }
    }
    cout<<ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}

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