oj.uz

Submission #674178

# Submission time Handle Problem Language Result Execution time Memory
674178 2022-12-23T11:34:16 Z stanislavpolyn Stranded Far From Home (BOI22_island) C++17
0 / 100
 1000 ms 39740 KB 
#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];

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

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9724 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 6 ms 9940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9724 KB Output is correct
3 Correct 150 ms 33528 KB Output is correct
4 Execution timed out 1090 ms 32984 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 233 ms 39740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 228 ms 35500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9724 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 6 ms 9940 KB Output isn't correct
5 Halted 0 ms 0 KB -