제출 #1217353

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

island

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 10, Limit = 5e6;
int n, m, a[N], iterations, val[N];
vector<int> g[N], seen;
bool vis[N];

void process(int v){
    int source = v;
    priority_queue<pair<int, int>> pq;
    ll sm = a[v];
    vis[v] = 1;
    seen.push_back(v);
    for (int u : g[v]){
        iterations++;
        if (!vis[u])
            pq.push({-a[u], u});
    }

    while (!pq.empty() and !val[source]){
        iterations++;
        auto [w, v] = pq.top();
        pq.pop();
        w = -w;
        if (w > sm) break;
        if (vis[v]) continue;
        if (val[v] == 1){
            val[source] = 1;
            break;
        }

        sm += w;
        vis[v] = 1;
        seen.push_back(v);
        for (int u : g[v]){
            iterations++;
            if (!vis[u]){
                pq.push({-a[u], u});
                if (a[u] <= sm and val[u] == 1)
                    val[source] = 1;
            }
        }
    }
}

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];

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

    vector<int> vec;
    for (int i = 1; i <= n; i ++)
        vec.push_back(i);
    shuffle(vec.begin(), vec.end(), rng);

    for (int v : vec){
        if (iterations > Limit) break;
        if (val[v]) continue;
        process(v);

        if (seen.size() == n or val[v] == 1)
            val[v] = 1;
        else{
            for (int x : seen)
                val[v] = -1;
        }

        for (int x : seen)
            vis[x] = 0;
        seen.clear();
    }

    for (int v = 1; v <= n; v ++){
        if (val[v]) continue;
        process(v);

        if (seen.size() == n or val[v] == 1)
            val[v] = 1;
        else{
            for (int x : seen)
                val[v] = -1;
        }

        for (int x : seen)
            vis[x] = 0;
        seen.clear();
    }

    for (int v = 1; v <= n; v ++)
        cout << (val[v] == 1 ? '1' : '0');
    cout << endl;
}

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