oj.uz

Submission #1041974

# Submission time Handle Problem Language Result Execution time Memory
1041974 2024-08-02T11:26:19 Z Blagoj Stranded Far From Home (BOI22_island) C++17
25 / 100
 84 ms 56568 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 2e5 + 100;

vector<ll> s(mxn), ldr(mxn), rnk(mxn), mx(mxn), p[mxn];

int Find(int x) {
    if (ldr[x] == x) return x;
    return ldr[x] = Find(ldr[x]);
}

void Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (rnk[x] < mx[y]) p[x].clear();
    if (rnk[y] < mx[x]) p[y].clear();
    if (p[x].size() < p[y].size()) swap(x, y);
    for (auto el : p[y]) p[x].push_back(el);
    ldr[y] = x;
    rnk[x] += rnk[y];
    mx[x] = max(mx[x], mx[y]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i];
    vector<pair<int, int>> edg;
    for (int i = 0; i < m; i++) {
        int f, t;
        cin >> f >> t;
        edg.push_back({f, t});
    }
    sort(all(edg), [&] (pair<int, int> a, pair<int, int> b) {
        return max(s[a.first], s[a.second]) < max(s[b.first], s[b.second]);
    });
    for (int i = 1; i <= n; i++) {
        ldr[i] = i;
        rnk[i] = s[i];
        p[i] = {i};
        mx[i] = s[i];
    }
    for (auto x : edg) Union(x.first, x.second);
    bitset<mxn> ans;
    for (auto x : p[Find(1)]) ans[x] = 1;
    for (int i = 1; i <= n; i++) cout << ans[i]; 
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is correct
2 Correct 3 ms 11356 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Runtime error 15 ms 23396 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11356 KB Output is correct
2 Correct 3 ms 11356 KB Output is correct
3 Correct 75 ms 26824 KB Output is correct
4 Correct 73 ms 37728 KB Output is correct
5 Correct 72 ms 29644 KB Output is correct
6 Correct 77 ms 30568 KB Output is correct
7 Correct 77 ms 30524 KB Output is correct
8 Correct 77 ms 35108 KB Output is correct
9 Correct 72 ms 33112 KB Output is correct
10 Correct 52 ms 22984 KB Output is correct
11 Correct 55 ms 25544 KB Output is correct
12 Correct 64 ms 26824 KB Output is correct
13 Correct 75 ms 39112 KB Output is correct
14 Correct 73 ms 37520 KB Output is correct
15 Correct 63 ms 27080 KB Output is correct
16 Correct 48 ms 25796 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11464 KB Output is correct
2 Correct 84 ms 31888 KB Output is correct
3 Correct 81 ms 32200 KB Output is correct
4 Correct 79 ms 40392 KB Output is correct
5 Correct 80 ms 39368 KB Output is correct
6 Correct 80 ms 31692 KB Output is correct
7 Correct 63 ms 26824 KB Output is correct
8 Correct 64 ms 26824 KB Output is correct
9 Correct 47 ms 25888 KB Output is correct
10 Correct 73 ms 31296 KB Output is correct
11 Correct 73 ms 32552 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11356 KB Output is correct
2 Runtime error 76 ms 56568 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 3 ms 11352 KB Output is correct
2 Correct 3 ms 11356 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Runtime error 15 ms 23396 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -