oj.uz

Submission #697787

# Submission time Handle Problem Language Result Execution time Memory
697787 2023-02-11T05:11:51 Z vjudge1 Stranded Far From Home (BOI22_island) C++17
0 / 100
 21 ms 16648 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;
        int 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);

    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:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Incorrect 7 ms 7540 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 7380 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Runtime error 21 ms 16648 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 20 ms 16632 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 16620 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 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Incorrect 7 ms 7540 KB Output isn't correct
5 Halted 0 ms 0 KB -