Submission #1305606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305606		AzeTurk810	Stranded Far From Home (BOI22_island)	C++20	0 / 100	116 ms	28152 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 <set>
#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
#define int ll

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

vector< int > ans;

struct DSU {
    vector<int> par , sum;
    vector< vector< int > > nodes;
    int n , components;
    bool can;

    DSU(int _n) {
        n = _n;
        components = n;
        par.assign(n , -1);
        sum.assign(n , -1);
        nodes.resize(n);
    }

    int Find(int u) {
        if(par[u] < 0 ) {
            can = ans[u];
            return u;
        }
        par[u] = Find(par[u]);
        ans[u] = ans[u] & can;
        can &= ans[u];
        return par[u];
    }

    bool Union(int u , int v) {
        u = Find(u);
        v = Find(v);
        if(u != v) {
            components--;
            if(par[u] > par[v]) {
                par[v] += par[u];
                par[u] = v;
                sum[v] += sum[u];
                return true;
            }
            par[u] += par[v];
            par[v] = u;
            sum[u] += sum[v];
            return true;
        } else {
            return false;
        }
    }
};

char solve() {
    int N , M;
    if(!(cin >> N >> M))
        return 1;
    vector< int > S(N + 1) , used(N + 1 , false);
    DSU t(N + 1);
    for(int i = 1;i <= N;i++)  {
        cin >> S[i];
        t.sum[i] = 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());
    // nums[0] = {-1 , -1};
    // reverse(nums.begin() + 1 , nums.end());
    ans.assign(N + 1 , 1);
    assert(nums.size() == N);
    for(const auto &[sz , v] : nums) {
        if(v == -1)
            continue;
        used[v] = true;
        for(const auto u : g[v]) {
            if(!used[u])
                continue;
            // cerr << v << ':' << u << endl;
            if(S[u] < S[v]) {
                int k = t.Find(u);
                if(t.sum[k] < S[v]) {
                    // cerr << k << '|' << v << endl;
                    ans[k] = false; 
                }
            }
            t.Union(v, u);
        }
    }
    // cerr << t.sum[t.Find(4)] << ln;
    for(int i = 1;i <= N;i++) {
        t.Find(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