제출 #1362482

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

island

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 200005;
vector <int> g[N];
int sz[N], szl[N], ans[N];

void dfs(int i, int p) {
    szl[i] = sz[i];
    for (int x : g[i]) {
        if (x == p) continue;
        dfs(x, i);
        szl[i] += szl[x];
    }
}

void dfs2(int i, int p) {
    if (i == 1 || ans[p] && szl[i] >= sz[p]) ans[i] = 1;
    for (int x : g[i]) dfs2(x, i);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) cin >> sz[i];
    for (int i = 1, u, v; i <= m; i ++) cin >> u >> v, g[min(u, v)].push_back(max(u, v));
    dfs(1, 0); dfs2(1, 0);
    for (int i = 1; i <= n; i ++) cout << ans[i];

    return 0;
}

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