oj.uz

Submission #697790

# Submission time Handle Problem Language Result Execution time Memory
697790 2023-02-11T05:19:03 Z vjudge1 Stranded Far From Home (BOI22_island) C++17
40 / 100
 1000 ms 48940 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++;
        }
        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 7 ms 14420 KB Output is correct
2 Correct 7 ms 14416 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 75 ms 14412 KB Output is correct
5 Correct 82 ms 14476 KB Output is correct
6 Correct 103 ms 14420 KB Output is correct
7 Correct 72 ms 14464 KB Output is correct
8 Correct 54 ms 14428 KB Output is correct
9 Correct 159 ms 14508 KB Output is correct
10 Correct 66 ms 14420 KB Output is correct
11 Correct 63 ms 14420 KB Output is correct
12 Correct 59 ms 14480 KB Output is correct
13 Correct 109 ms 14412 KB Output is correct
14 Correct 64 ms 14484 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 7 ms 14336 KB Output is correct
3 Execution timed out 1085 ms 46868 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14344 KB Output is correct
2 Correct 684 ms 46876 KB Output is correct
3 Correct 706 ms 47992 KB Output is correct
4 Correct 783 ms 48216 KB Output is correct
5 Correct 642 ms 48224 KB Output is correct
6 Correct 530 ms 46664 KB Output is correct
7 Correct 251 ms 48940 KB Output is correct
8 Correct 226 ms 47036 KB Output is correct
9 Correct 262 ms 32964 KB Output is correct
10 Correct 686 ms 46676 KB Output is correct
11 Correct 461 ms 46692 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14416 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 75 ms 14412 KB Output is correct
5 Correct 82 ms 14476 KB Output is correct
6 Correct 103 ms 14420 KB Output is correct
7 Correct 72 ms 14464 KB Output is correct
8 Correct 54 ms 14428 KB Output is correct
9 Correct 159 ms 14508 KB Output is correct
10 Correct 66 ms 14420 KB Output is correct
11 Correct 63 ms 14420 KB Output is correct
12 Correct 59 ms 14480 KB Output is correct
13 Correct 109 ms 14412 KB Output is correct
14 Correct 64 ms 14484 KB Output is correct
15 Correct 9 ms 14292 KB Output is correct
16 Correct 7 ms 14336 KB Output is correct
17 Execution timed out 1085 ms 46868 KB Time limit exceeded
18 Halted 0 ms 0 KB -