oj.uz

Submission #697791

# Submission time Handle Problem Language Result Execution time Memory
697791 2023-02-11T05:25:07 Z vjudge1 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 43868 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] && mark[v])
                join(u, v);
            j++;
        }

        vector<int> er;
        for (int it: st) if (j < n && sum[it] < s[idx[j]]) {
            for (int k: node[it]) mark[k] = 0;
            er.push_back(it);
        }
        for (int it: er) st.erase(it);
        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:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
island.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         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 8 ms 14292 KB Output is correct
3 Correct 7 ms 14328 KB Output is correct
4 Correct 75 ms 14548 KB Output is correct
5 Correct 79 ms 14420 KB Output is correct
6 Correct 101 ms 14464 KB Output is correct
7 Correct 72 ms 14464 KB Output is correct
8 Correct 53 ms 14420 KB Output is correct
9 Correct 137 ms 14420 KB Output is correct
10 Correct 70 ms 14476 KB Output is correct
11 Correct 65 ms 14420 KB Output is correct
12 Correct 58 ms 14420 KB Output is correct
13 Correct 108 ms 14472 KB Output is correct
14 Correct 63 ms 14476 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Execution timed out 1084 ms 43572 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 1093 ms 43324 KB Time limit exceeded
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 356 ms 43868 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 8 ms 14292 KB Output is correct
3 Correct 7 ms 14328 KB Output is correct
4 Correct 75 ms 14548 KB Output is correct
5 Correct 79 ms 14420 KB Output is correct
6 Correct 101 ms 14464 KB Output is correct
7 Correct 72 ms 14464 KB Output is correct
8 Correct 53 ms 14420 KB Output is correct
9 Correct 137 ms 14420 KB Output is correct
10 Correct 70 ms 14476 KB Output is correct
11 Correct 65 ms 14420 KB Output is correct
12 Correct 58 ms 14420 KB Output is correct
13 Correct 108 ms 14472 KB Output is correct
14 Correct 63 ms 14476 KB Output is correct
15 Correct 7 ms 14292 KB Output is correct
16 Correct 7 ms 14420 KB Output is correct
17 Execution timed out 1084 ms 43572 KB Time limit exceeded
18 Halted 0 ms 0 KB -