oj.uz

Submission #697789

# Submission time Handle Problem Language Result Execution time Memory
697789 2023-02-11T05:17:37 Z vjudge1 Stranded Far From Home (BOI22_island) C++17
10 / 100
 131 ms 15596 KB 
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define fi first
#define se second
#define sz(x) (int)x.size()
#define rep(i, b, e) for (int i = (b); i <= (e); i++)
#define rrep(i, b, e) for (int i = (b); i >= (e); i--)

typedef long long ll;
typedef pair<ll, ll> ii;

template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}

const int N = 1e5 + 7;

int n, m, s[N];
vector<int> adj[N];

void read() {
    cin >> n >> m;
    rep(i, 1, n) cin >> s[i];
    rep(i, 1, m) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

void sub1() {
    rep(i, 1, n) {
        priority_queue<ii> pq;
        vector<bool> done(n + 1, 0);
        queue<int> q; q.push(i); done[i] = 1;
        ll cur = s[i], cnt = 0;
        while (sz(q)) {
            int u = q.front(); q.pop();
            for (int v: adj[u]) if (!done[v]) {
                pq.push({-s[v], v});
                done[v] = 1;
            }
            while (sz(pq)) {
                ii k = pq.top();
                if (cur >= -k.fi) {
                    ++cnt; pq.pop();
                    cur += -k.fi;
                    q.push(k.se);
                } else break;
            }
        }
        if (cnt == n - 1) cout << 1; else cout << 0;
    }
}

ll sum[N];
int dsu[N];
bool mark[N];
set<int> st, node[N];
int root(int x){
    return (dsu[x] < 0 ? x : dsu[x] = root(dsu[x]));
}

void join(int x, int y) {
    if ((x = root(x)) == (y = root(y))) return;
    if (sz(node[x]) < sz(node[y])) swap(x, y);
    for (int i: node[y]) node[x].insert(i);
    node[y].clear();

    dsu[x] += dsu[y]; sum[x] += sum[y];
    dsu[y] = x; sum[y] = 0;
    st.erase(y);
}

void full() {
    memset(dsu, -1, sizeof dsu);
    vector<int> idx;
    rep(i, 1, n) {
        idx.push_back(i);
        st.insert(i);
        sum[i] = s[i];
        mark[i] = 1;
        node[i].insert(i);
    }
    sort(idx.begin(), idx.end(), [&](int i, int j){
         return s[i] < s[j];
    });
    rep(i, 0, n - 1) {
        int j = i;
        while (j < n && s[idx[j]] == s[idx[i]]) {
            int u = idx[j];
            for (int v: adj[u]) if (s[v] <= s[u])
                join(u, v);
            j++;
        }
        for (int i: st) if (j < n && sum[i] < s[idx[j]]) {
            for (int k: node[i]) mark[k] = 0;
        }
        i = j - 1;
    }
    rep(i, 1, n) cout << mark[i];
}

void solve() {
    if (n <= 2000) sub1();
    else full();
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    read();
    solve();
}


/**
+ check mod (gõ đúng số), limit, kiểu dữ liệu
+ check format output
+mấy bài multitest:
    quên reset biến, mảng, (nên dùng fill, memset, v.v)
    quên xuống dòng
    precompute đầu bài
+nhập hết dữ liệu trước khi return
+xóa debug
**/

Compilation message

island.cpp: In function 'int main()':
island.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
island.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Correct 71 ms 7424 KB Output is correct
5 Correct 74 ms 7392 KB Output is correct
6 Correct 95 ms 7456 KB Output is correct
7 Correct 70 ms 7424 KB Output is correct
8 Correct 49 ms 7444 KB Output is correct
9 Correct 131 ms 7508 KB Output is correct
10 Correct 69 ms 7476 KB Output is correct
11 Correct 58 ms 7472 KB Output is correct
12 Correct 57 ms 7512 KB Output is correct
13 Correct 104 ms 7452 KB Output is correct
14 Correct 62 ms 7380 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 5 ms 7368 KB Output is correct
3 Runtime error 19 ms 15460 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Runtime error 22 ms 15596 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Runtime error 19 ms 15444 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Correct 71 ms 7424 KB Output is correct
5 Correct 74 ms 7392 KB Output is correct
6 Correct 95 ms 7456 KB Output is correct
7 Correct 70 ms 7424 KB Output is correct
8 Correct 49 ms 7444 KB Output is correct
9 Correct 131 ms 7508 KB Output is correct
10 Correct 69 ms 7476 KB Output is correct
11 Correct 58 ms 7472 KB Output is correct
12 Correct 57 ms 7512 KB Output is correct
13 Correct 104 ms 7452 KB Output is correct
14 Correct 62 ms 7380 KB Output is correct
15 Correct 4 ms 7252 KB Output is correct
16 Correct 5 ms 7368 KB Output is correct
17 Runtime error 19 ms 15460 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -