Submission #750598

#	Time	Username	Problem	Language	Result	Execution time	Memory
750598		Rasoul006	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1091 ms	524288 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] , pa[N] , sz[N] ;

vector <ll> g[N] ;

string s ;

void dfs (ll u , ll p)
{
    pa[u] = p ;

    sz[u] = a[u] ;

    for (auto it : g[u])
    {
        if (it == p) continue ;

        dfs(it , u) ;
        sz[u] += sz[it] ;
    }

}

void dfs2 (ll u , ll p)
{
    s[u-1] = '1' ;

    for (auto it : g[u])
    {
        if (sz[it] < a[u] || it == p) continue ;
        dfs2 (it , u) ;
    }
}

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

    cin >> n >> m ;

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

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

    dfs (1 , 1) ;

    dfs2 (1 , 1) ;


    cout << s << endl ;

    return 0;
}

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