oj.uz

답안 #674183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
674183 2022-12-23T11:50:48 Z stanislavpolyn Stranded Far From Home (BOI22_island) C++17
0 / 100
 242 ms 35528 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;

//    cout << "GO " << v << " " << sum << "\n";
    fe (to, g[v]) {
        q.insert({a[to], to});
        vis[to] = 1;
    }
    while (sz(q)) {
//        cout << "FROM " << v << "\n";

        int v = q.begin()->se;
        q.erase(q.begin());

//        cout << "GO " << v << " " << a[v] << "\n";

        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 rnd(int l, int r) {
    return rng() % (r - l + 1) + l;
}

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];
//        a[i] = rnd(1, 20);
//        cout << a[i] << " ";
        u.pb({a[i], i});
    }
//    cout << "\n";

    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)) {
            int ptr2 = ptr;
            while (ptr2 < sz(u) && u[ptr2].fi == u[ptr].fi) {
                fe (to, g[u[ptr].se]) {
                    if (a[to] < u[ptr].fi) {
                        int v = root(to);
                        if (sum[v] < u[ptr].fi) {
                            fe (cur, ::v[v]) {
                                bad[cur] = 1;
                            }
                        }
                    }
                }
                ptr2++;
            }
        }

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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9728 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Incorrect 7 ms 9940 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9728 KB Output is correct
3 Incorrect 149 ms 29164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9700 KB Output is correct
2 Incorrect 242 ms 35528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9720 KB Output is correct
2 Incorrect 214 ms 30968 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9728 KB Output is correct
4 Correct 6 ms 9812 KB Output is correct
5 Incorrect 7 ms 9940 KB Output isn't correct
6 Halted 0 ms 0 KB -