Submission #1305520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305520		AzeTurk810	Stranded Far From Home (BOI22_island)	C++20	0 / 100	174 ms	15336 KiB

island

/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

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

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18

#ifdef ONPC
    #include<algo.hpp>
#else
    #define dbg(...)
#endif

char solve() {
    int N , M;
    if(!(cin >> N >> M))
        return 1;
    vector< int > S(N + 1);
    for(int i = 1;i <= N;i++) 
        cin >> S[i];
    vector< vector< int > > g(N + 1);
    for(int i = 0;i < M;i++) {
        int u , v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector< pair< int , int > > nums;
    for(int i = 1;i <= N;i++) {
        nums.push_back(make_pair(S[i], i));
    }
    sort(nums.begin() , nums.end() , greater<>());
    vector< int > ans(N + 1);
    assert(nums.size() == N);
    vector< int > used(N + 1);
    int idx = 1;

    auto bfs = [&] (int st) {
        priority_queue< pair<int , int > , vector< pair< int , int > > , greater<> > pq;
        int cur = S[st];
        for(int u : g[st]) {
            pq.push({S[u] , u});
        }
        while (!pq.empty()) {
            auto [w , v] = pq.top();
            dbg(v);
            pq.pop();
            if(w > cur)
                return false;
            if(ans[v])
                return true;
            cur += w;
            for(auto u : g[v]) {
                    dbg(u);
                    dbg(used[u]);
                if(used[u] < idx) {
                    pq.push({S[u] , u});
                    used[u] = max(used[u] , idx);
                }
            }
        }
        return true;
    };

    for(int i = 0;i < N;i++) {
        dbg(nums[i].second);
        int v = nums[i].second;
        ans[v] = bfs(v);
        idx++;
    }
    for(int i = 1;i <= N;i++) {
        cout << ans[i];
    }
    cout << ln;
    return 0;
}

// Attack on titan<3

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int t = 1e9;
    //cin >> t;
    for(int cases = 0 ; cases < t;cases ++) {
        if(solve())
            break;
        #ifdef ONPC
        cerr << "__________\n";
        #endif
    }
}
// Just Imaginary

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