Submission #750585

#	Time	Username	Problem	Language	Result	Execution time	Memory
750585		Rasoul006	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1080 ms	42764 KiB

island

#include <bits/stdc++.h>

#define endl "\n"

#define F first

#define S second

#define pb push_back

#define all(x) x.begin() , x.end()

#define mm(dp , val) memset (dp , val , sizeof dp)

#define mid ((r+l)>>1)

#define lx (n<<1)

#define rx ((n<<1)|1)

#define low (i&(-i))

#define lb lower_bound

#define ub upper_bound

#define no void (cout << "NO" << endl)

#define one void (cout << "-1" << endl)

#define zer void (cout << "0" << endl)

#define yes void (cout << "YES" << endl)

typedef long long ll;

using namespace std;

const int logn = 26 ;

const int N = 1e6+5;

const int mod = 1e9+7;

const long long oo = 4557430888798830399 ;

ll dx[] = {0 , 0 , 1 , -1};
ll dy[] = {1 , -1 , 0 , 0};

ll n , m , a[N] , all ;

vector <pair <ll,ll>> g[N] ;

set <pair <ll,ll>> st ;

bool vis[N] ;

bool bfs (ll i)
{
    ll tot = 0 ;

    st.insert ({a[i] , i}) ;

    while (!st.empty())
    {
        pair <ll,ll> p = *st.begin() ;
        st.erase(st.begin()) ;

        ll u = p.S , val = p.F ;
//
//        cout << u << " " << a[u] << " " << tot << endl ;

        if (tot < val && tot != 0) break ;

        tot += val ;
        vis[u] = true ;


        for (auto it : g[u])
        {
            if (!vis[it.S])
                st.insert(it) ;
            vis[it.S] = true ;
        }
    }

    st.clear();
    for (int i = 1 ; i<=n ; ++i)
        vis[i] = false ;

    return (tot == all) ;
}

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

    cin >> n >> m ;

    string s = "" ;

    for (int i = 1 ; i<=n ; i++)
        cin >> a[i] , s += '0' , all += a[i] ;

    for (int i = 0 ; i<m ; i++)
    {
        ll u , v ;
        cin >> u >> v ;
        g[u].pb({a[v] , v}) ;
        g[v].pb({a[u] ,u}) ;
    }

    for (int i = 1 ; i<=n ; i++)
        s[i-1] = (bfs(i) ? '1' : '0') ;

    cout << s << endl ;

    return 0;
}

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