oj.uz

Submission #599464

# Submission time Handle Problem Language Result Execution time Memory
599464 2022-07-19T14:21:13 Z SlavicG Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 361012 KB 
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

const int N = 2e5 + 10;
ll cnt[N], p[N], c[N], mx[N];
set<int> s[N];
vector<int> adj[N];
int get(int a) {return p[a] = (p[a] == a ? a : get(p[a]));}

void uni(int a, int b) {
    a = get(a), b = get(b);
    if(a == b) return;

    p[a] = b;
    if(cnt[a] >= c[b]) {
        for(auto x: s[a]) s[b].insert(x);
    }
    cnt[b] += cnt[a];
}
int main() {
    int n, m; cin >> n >> m;
    vector<pair<int, int>> paiu;
    for(int i = 0; i < n; ++i) {
        cin >> c[i];
        paiu.push_back({c[i], i});
    }
    for(int i = 0; i < n; ++i) {
        p[i] = i;
        cnt[i] = c[i];
        s[i].insert(i);
    }
    sort(paiu.begin(), paiu.end());
    vector<bool> vis(n, false);
    for(int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 0; i < n; ++i) {
        int u = paiu[i].second;
        for(int v: adj[u]) {
            if(!vis[v]) continue;
            uni(v, u);
        }
        vis[u] = true;
    }
    vector<int> ans(n, 0);
    for(auto x: s[paiu.back().second]) ans[x] = 1;
    for(auto x: ans) cout << x;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 11 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 122 ms 30772 KB Output is correct
5 Correct 20 ms 18516 KB Output is correct
6 Correct 78 ms 40260 KB Output is correct
7 Correct 53 ms 30156 KB Output is correct
8 Correct 51 ms 27416 KB Output is correct
9 Correct 166 ms 61516 KB Output is correct
10 Correct 22 ms 15108 KB Output is correct
11 Correct 12 ms 15188 KB Output is correct
12 Correct 15 ms 14956 KB Output is correct
13 Correct 289 ms 105368 KB Output is correct
14 Correct 17 ms 16192 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14312 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Execution timed out 1058 ms 355292 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 712 ms 143708 KB Output is correct
3 Correct 724 ms 146788 KB Output is correct
4 Execution timed out 1096 ms 361012 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14428 KB Output is correct
2 Execution timed out 1085 ms 311820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 11 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 122 ms 30772 KB Output is correct
5 Correct 20 ms 18516 KB Output is correct
6 Correct 78 ms 40260 KB Output is correct
7 Correct 53 ms 30156 KB Output is correct
8 Correct 51 ms 27416 KB Output is correct
9 Correct 166 ms 61516 KB Output is correct
10 Correct 22 ms 15108 KB Output is correct
11 Correct 12 ms 15188 KB Output is correct
12 Correct 15 ms 14956 KB Output is correct
13 Correct 289 ms 105368 KB Output is correct
14 Correct 17 ms 16192 KB Output is correct
15 Correct 9 ms 14312 KB Output is correct
16 Correct 9 ms 14420 KB Output is correct
17 Execution timed out 1058 ms 355292 KB Time limit exceeded
18 Halted 0 ms 0 KB -