Submission #744433

#	Time	Username	Problem	Language	Result	Execution time	Memory
744433		bgnbvnbv	Stranded Far From Home (BOI22_island)	C++14	100 / 100	169 ms	42304 KiB

island

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll lab[maxN];
ll sum[maxN];
ll findset(ll x)
{
    return lab[x]<0?x:lab[x]=findset(lab[x]);
}
vector<ll>vec[maxN];
void unite(ll u,ll v,ll w)
{
    u=findset(u);
    v=findset(v);
    if(u==v) return;
    if(lab[u]>lab[v]) swap(u,v);
    if(sum[u]<w)
    {
        if(sum[v]<w)
        {
            vec[u].clear();
        }
        else
        {
            swap(vec[u],vec[v]);
        }
        vec[v].clear();
    }
    else
    {
        if(sum[v]>=w)
        {
            for(auto zz:vec[v]) vec[u].pb(zz);
        }
        vec[v].clear();
    }
    sum[u]+=sum[v];
    lab[u]+=lab[v];
    lab[v]=u;
}
ll n,m,ans[maxN],a[maxN];
struct edge
{
    ll u,v,w;
    bool operator<(const edge&o)
    {
        return w<o.w;
    }
}e[maxN];
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i],vec[i].pb(i),ans[i]=0,sum[i]=a[i],lab[i]=-1;
    for(int i=1;i<=m;i++)
    {
        cin >> e[i].u >> e[i].v;
        e[i].w=max(a[e[i].u],a[e[i].v]);
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=m;i++)
    {
        unite(e[i].u,e[i].v,e[i].w);
    }
    ll x=findset(1);
    for(auto zz:vec[x])
    {
        ans[zz]=1;
    }
    for(int i=1;i<=n;i++) cout << ans[i];

}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

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