제출 #697798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
697798		Duy_e	Stranded Far From Home (BOI22_island)	C++14	20 / 100	1094 ms	30556 KiB

island

#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define st first
#define nd second
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
using namespace std;

const long long INF = 1e18;
const long long N = 2e5 + 7;

int n, m;
ll mx;
ll s[N];
vector <int> d[N];

namespace sub14 {
    vector <int> save;
    bool vis[N];

    bool check(int st) {
        priority_queue <pii, vector <pii>, greater <pii>> q;
        for (int i: save) vis[i] = false;
        save.clear();
        for (int u: d[st]) {
            vis[u] = true;
            save.push_back(u);
            q.push({s[u], u});
        }

        ll cur = s[st];
        vis[st] = true;
        save.push_back(st);
        ll tar = mx;
        while (q.size()) {
            int u = q.top().nd, w = q.top().st; q.pop();
            if (cur < w) return false;
            cur += w;
            if (cur >= tar) return true;

            for (int v: d[u]) if (!vis[v]) {
                vis[v] = true;
                save.push_back(v);
                q.push({s[v], v});
            }
        }

        return true;
    }
}

namespace sub2 {

    bool ck[N];
    ll f[N];

    void dfs(int p, int u) {
        f[u] = s[u];
        for (int v: d[u]) if (v != p) {
            dfs(u, v);
            f[u] += f[v];
        }

        ck[u] = f[u] >= s[p];
    }

    void dfs2(int p, int u) {
        for (int v: d[u]) if (v != p) {
            ck[v] &= ck[u];
            dfs2(u, v);
        }
    }

    void solve() {
        ck[1] = true;
        dfs(1, 1);
        dfs2(1, 1);
        rep(i, 1, n) cout << ck[i];
    }
}

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

    cin >> n >> m;

    rep(i, 1, n) {
        cin >> s[i];
        mx = max(mx, s[i]);
    }

    rep(i, 1, m) {
        int u, v;
        cin >> u >> v;
        d[u].push_back(v);
        d[v].push_back(u);
    }

    bool is_sub2 = true;
    if (m != n - 1) is_sub2 = false;
    rep(i, 2, n) if (s[i] > s[i - 1]) is_sub2 = false;

    if (is_sub2) {
        sub2::solve();
        return 0;
    }

    rep(i, 1, n)
        cout << sub14 :: check(i);

    return 0;
}

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