제출 #722894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
722894		The_Samurai	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1082 ms	15292 KiB

island

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
int INF = 2e9;

int n, m, mx;
vector<vector<int>> g;
vector<int> a, ans;

bool check(int i) {
    int sum = a[i];
    if (sum >= mx) return true;
    priority_queue<pair<int, int>> pq;
    bitset<200001> bs;
    bs[i] = 1;
    vector<int> way = {i};
    for (int u : g[i]) {
        bs[u] = 1;
        pq.push({-a[u], u});
    }
    while (!pq.empty()) {
        auto [need, u] = pq.top();
        pq.pop();
        need = -need;
        if (sum < need) break;
        way.emplace_back(u);
        sum += need;
        if (sum >= mx) {
            for (int v : g[i]) {
                if (a[i] <= a[v]) {
                    ans[v] = 1;
                }
            }
            return true;
        }
        for (int v : g[u]) {
            if (!bs[v]) {
                bs[v] = 1;
                pq.push({-a[v], v});
            }
        }
    }
    for (int x: way) ans[x] = 0;
    return false;
}

void solve() {
    cin >> n >> m;
    a.assign(n + 1, 0);
    g.assign(n + 1, {});
    ans.assign(n + 1, -1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    mx = *max_element(a.begin() + 1, a.end());
    for (int i = 1; i <= n; i++) {
        if (ans[i] != -1) {
            cout << ans[i];
            continue;
        }
        cout << check(i);
    }
}

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

    int queries = 1;
#ifdef test_cases
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin >> queries;
#else
    //    cin >> queries;
#endif

    for (int test_case = 1; test_case <= queries; test_case++) {
        solve();
//        cout << '\n';
    }
}

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