Submission #674181

#	Time	Username	Problem	Language	Result	Execution time	Memory
674181		stanislavpolyn	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1093 ms	35488 KiB

island

#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()

using namespace std;

mt19937_64 rng(228);

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umn(T& a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T>
bool umx(T& a, T b) { return a < b ? a = b, 1 : 0; }

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

const int N = 2e5 + 5;

int n, m;
int a[N];
ve<int> g[N];
ve<pii> u;

ve<int> v[N];
int link[N];
ll sum[N];

int root(int x) {
    if (link[x] == x) return x;
    else return root(link[x]);
}

void uni(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) {
        return;
    }
    if (sz(v[a]) > sz(v[b])) swap(a, b);

    sum[b] += sum[a];
    link[a] = b;
    fe (x, v[a]) v[b].pb(x);
}

bool bad[N];

bool brute(int v) {
    ll sum = 0;
    set<pii> q;
    ve<bool> vis(n + 1);
    sum = a[v];
    vis[v] = 1;
    fe (to, g[v]) {
        q.insert({a[to], to});
        vis[to] = 1;
    }
    while (sz(q)) {
        int v = q.begin()->se;
        q.erase(q.begin());

        if (a[v] > sum) {
            return 0;
        }

        sum += a[v];
        fe (to, g[v]) {
            if (!vis[to]) {
                vis[to] = 1;
                q.insert({a[to], to});
            }
        }
    }
    return 1;
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> n >> m;

    fr (i, 1, n) {
        cin >> a[i];
        u.pb({a[i], i});
    }

    fr (i, 1, m) {
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }

    sort(all(u));

//    fe (x, a) {
//        cout << x.fi << " " << x.se << "\n";
//    }

    fr (i, 1, n) {
        link[i] = i;
        sum[i] = a[i];
        v[i] = {i};
    }

    fr (i, 0, sz(u) - 1) {
        int ptr = i;
        ve<int> ver;
        while (ptr < sz(u) && u[ptr].fi == u[i].fi) {
            ver.pb(u[ptr].se);
            fe (to, g[u[ptr].se]) {
                if (a[to] <= u[i].fi) {
                    uni(u[ptr].se, to);
                }
            }
            ptr++;
        }

//        cout << "added <= " << u[ptr - 1].fi << "\n";


        if (ptr < sz(u)) {
            fe (x, ver) {
                int v = root(x);

                if (sum[v] < u[ptr].fi) {
                    fe (cur, ::v[v]) {
                        bad[cur] = 1;
                    }
                }
            }
        }

        i = ptr - 1;
    }

//    fr (i, 1, n) {
//        cout << !bad[i];
//    }
//    cout << "\n";

    fr (i, 1, n) {
        cout << brute(i);
    }
    cout << "\n";

    return 0;
}

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