oj.uz

Submission #674181

# Submission time Handle Problem Language Result Execution time Memory
674181 2022-12-23T11:42:31 Z stanislavpolyn Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 35488 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];

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9732 KB Output is correct
4 Correct 194 ms 9944 KB Output is correct
5 Correct 196 ms 10056 KB Output is correct
6 Correct 296 ms 9932 KB Output is correct
7 Correct 187 ms 9940 KB Output is correct
8 Correct 138 ms 9812 KB Output is correct
9 Correct 309 ms 9992 KB Output is correct
10 Correct 118 ms 9992 KB Output is correct
11 Correct 96 ms 9940 KB Output is correct
12 Correct 119 ms 10008 KB Output is correct
13 Correct 194 ms 9940 KB Output is correct
14 Correct 119 ms 9952 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Execution timed out 1083 ms 30064 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9724 KB Output is correct
2 Execution timed out 1076 ms 35488 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9684 KB Output is correct
2 Execution timed out 1093 ms 31164 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9732 KB Output is correct
4 Correct 194 ms 9944 KB Output is correct
5 Correct 196 ms 10056 KB Output is correct
6 Correct 296 ms 9932 KB Output is correct
7 Correct 187 ms 9940 KB Output is correct
8 Correct 138 ms 9812 KB Output is correct
9 Correct 309 ms 9992 KB Output is correct
10 Correct 118 ms 9992 KB Output is correct
11 Correct 96 ms 9940 KB Output is correct
12 Correct 119 ms 10008 KB Output is correct
13 Correct 194 ms 9940 KB Output is correct
14 Correct 119 ms 9952 KB Output is correct
15 Correct 5 ms 9728 KB Output is correct
16 Correct 7 ms 9684 KB Output is correct
17 Execution timed out 1083 ms 30064 KB Time limit exceeded
18 Halted 0 ms 0 KB -