Submission #1305554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305554		thesentro	Stranded Far From Home (BOI22_island)	C++20	0 / 100	148 ms	808 KiB

island

/*
 _____ _          ____             _             
|_   _| |__   ___/ ___|  ___ _ __ | |_ _ __ ___  
  | | | '_ \ / _ \___ \ / _ \ '_ \| __| '__/ _ \ 
  | | | | | |  __/___) |  __/ | | | |_| | | (_) |
  |_| |_| |_|\___|____/ \___|_| |_|\__|_|  \___/ 
*/
 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
ll mod = 1e9+7;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll binpow(ll a, ll b)
{
    ll res = 1;
    while (b>0)
    {
        if (b&1)
            res = (res*a)%mod;
        a = (a*a)%mod;
        b>>=1;
    }
    return res;
}
ll gcd(ll x, ll y)
{
    if (y==0)
        return x;
    return gcd(y, x%y);
}
ll maxi = 2002;
vector<set<pair<ll,ll>>>g(maxi);
vector<ll>vis(maxi, 0);
vector<ll>v(maxi);
ll val = 0;
ll cnt = 0;
void bfs(ll x)
{
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>>pq;
    pq.push({v[x],x});
    val = v[x];
    vis[x] = 1;
    while (!pq.empty())
    {
        auto it= pq.top();
        pq.pop();
        ll t = it.second;
        for (auto itr:g[t])
        {
            ll i = itr.second;
            if (vis[i]) continue;
            if (v[i]<=val)
            {
                val += v[i];
                pq.push({v[i], i});
                vis[i] = 1;
            }
        }
    }
}
void solve()
{   
    ll n,m;
    cin>>n>>m;
    for (int i=1 ; i<=n ;i++) cin>>v[i];
    for (int i=1 ; i<=m ;i++)
    {
        ll x,y;
        cin>>x>>y;
        g[x].insert({v[y],y});
        g[y].insert({v[x],x});
    }
    for (int i=1 ; i<=n ;i++)
    {
        vis.assign(n+1,0 );
        bfs(i);
        ll cnt = 0;
        for (int j=1 ; j<=n ;j++) cnt += vis[j];
        // for (int j=1 ; j<=n ;j++)
        //     cout<<vis[j]<<" ";
 
        if (cnt==n)
            cout<<1;
        else
            cout<<0;
    }
}
int main()
{
    ll tt = 1;
    // cin>>tt;
    while (tt--)
    {
        solve();
    }
    return 0;
}

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