Submission #968446

#	Time	Username	Problem	Language	Result	Execution time	Memory
968446		maxFedorchuk	Stranded Far From Home (BOI22_island)	C++17	100 / 100	91 ms	17084 KiB

island

#include <bits/stdc++.h>
using namespace std;

const long long MX=2e5+10;
long long s[MX],ld[MX],ans[MX],sm[MX];

int get_ld(int zar)
{
    if(zar==ld[zar])
    {
        return zar;
    }

    int o=get_ld(ld[zar]);
    ans[zar]=min(ans[zar],ans[ld[zar]]);

    ld[zar]=o;
    return ld[zar];
}

void adrb(int a,int b)
{
    a=get_ld(a);
    b=get_ld(b);

    if(a==b)
    {
        return;
    }

    if(sm[a]<s[b])
    {
        ans[a]=0;
    }

    sm[b]+=sm[a];
    ld[a]=b;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        ld[i]=i;
        ans[i]=1;
        sm[i]=s[i];
    }

    vector < pair < int , pair < int , int > > > ms;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;

        if(s[a]>s[b])
        {
            swap(a,b);
        }

        ms.push_back({s[b],{a,b}});
    }

    sort(ms.begin(),ms.end());

    for(auto u:ms)
    {
        adrb(u.second.first,u.second.second);
    }

    for(int i=1;i<=n;i++)
    {
        get_ld(i);
        cout<<ans[i];
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35