제출 #1362247

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1362247		digitaldreamer	Stranded Far From Home (BOI22_island)	C++20	10 / 100	663 ms	589824 KiB

island

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mid (l + ((r - l) / 2))
#define F first
#define S second

vector<int64_t> dp(2e5 + 5), a(2e5 + 5) ;
vector<vector<int64_t>> adj(2e5 + 5) ;
vector<bool> an(2e5 + 5) ;

void dfs(int64_t nd , int64_t par)
{
    dp[nd] = a[nd] ;
    for(auto it : adj[nd])
    {
        if(it == par) continue ;
        dfs(it , nd), dp[nd] += dp[it] ;
    }
    return ;
}

void dfs2(int64_t nd , int64_t par , bool op)
{
    if(dp[nd] < a[par]) op = 0 ;
    an[nd] = op ;
    for(auto it : adj[nd])
    {
        if(it == par) continue ;
        dfs2(it , nd , op) ;
    }
    return ;
}

void solve()
{
    int64_t n, m ;
    cin >> n >> m ;
    for(int64_t i = 1 ; i <= n ; i++) cin >> a[i] ;
    for(int64_t i = 1 ; i <= m ; i++)
    {
        int64_t x, y ;
        cin >> x >> y ;
        adj[x].pb(y), adj[y].pb(x) ;
    }
    dfs(1 , 0), dfs2(1 , 0 , 1) ;
    /*for(int64_t i = 1 ; i <= n ; i++) cout << dp[i] << ' ' ;
    cout << endl;*/
    for(int64_t i = 1 ; i <= n ; i++) cout << an[i] ;
    cout << endl;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1 ;
    //cin >> tt;
    while (tt--) solve() ;
}

• 서브태스크 1: 0 / 10
• 서브태스크 2: 10 / 10
• 서브태스크 3: 0 / 15
• 서브태스크 4: 0 / 30
• 서브태스크 5: 0 / 35