oj.uz

Submission #697793

# Submission time Handle Problem Language Result Execution time Memory
697793 2023-02-11T05:47:50 Z vjudge1 Stranded Far From Home (BOI22_island) C++17
10 / 100
 614 ms 43664 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 = 2e5 + 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++;
        }

        rep(k, i, j - 1) {
            int u = idx[j];
            for (int v: adj[u]) if (s[v] > s[u] && sum[root(v)] < s[v]) {
                int it = root(v);
                for (int k: node[it]) mark[k] = 0;
                node[it].clear();
            }
        }
        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:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
island.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14312 KB Output is correct
4 Correct 75 ms 14420 KB Output is correct
5 Correct 77 ms 14472 KB Output is correct
6 Correct 102 ms 14464 KB Output is correct
7 Correct 71 ms 14420 KB Output is correct
8 Correct 55 ms 14456 KB Output is correct
9 Correct 137 ms 14420 KB Output is correct
10 Correct 66 ms 14476 KB Output is correct
11 Correct 62 ms 14580 KB Output is correct
12 Correct 58 ms 14476 KB Output is correct
13 Correct 109 ms 14476 KB Output is correct
14 Correct 64 ms 14420 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Incorrect 253 ms 43664 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 588 ms 43556 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Incorrect 614 ms 43612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14312 KB Output is correct
4 Correct 75 ms 14420 KB Output is correct
5 Correct 77 ms 14472 KB Output is correct
6 Correct 102 ms 14464 KB Output is correct
7 Correct 71 ms 14420 KB Output is correct
8 Correct 55 ms 14456 KB Output is correct
9 Correct 137 ms 14420 KB Output is correct
10 Correct 66 ms 14476 KB Output is correct
11 Correct 62 ms 14580 KB Output is correct
12 Correct 58 ms 14476 KB Output is correct
13 Correct 109 ms 14476 KB Output is correct
14 Correct 64 ms 14420 KB Output is correct
15 Correct 8 ms 14292 KB Output is correct
16 Correct 7 ms 14292 KB Output is correct
17 Incorrect 253 ms 43664 KB Output isn't correct
18 Halted 0 ms 0 KB -