oj.uz

Submission #599493

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

const int N = 2e5 + 10;
ll cnt[N], p[N], c[N];
set<ll> s[N];
vector<ll> adj[N];

ll get(ll a) {return p[a] = (p[a] == a ? a : get(p[a]));}

void uni(ll a, ll b, ll vb) {
    a = get(a), b = get(b);
    if(a == b) return;
    if(cnt[a] >= vb) {
        for(auto x: s[a]) s[b].insert(x);
    }

    p[a] = b;
    cnt[b] += cnt[a];
}
int main() {
    int n, m; cin >> n >> m;
    vector<pair<ll, ll>> 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) {
        ll u = paiu[i].second;
        for(int v: adj[u]) {
            if(!vis[v]) continue;
            uni(v, u, c[u]);
        }
        vis[u] = true;
    }

    vector<int> ans(n, 0);
    for(auto x: s[get(paiu[n - 1].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 10 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 64 ms 30732 KB Output is correct
5 Correct 36 ms 18536 KB Output is correct
6 Correct 106 ms 40268 KB Output is correct
7 Correct 52 ms 30156 KB Output is correct
8 Correct 46 ms 27560 KB Output is correct
9 Correct 140 ms 61444 KB Output is correct
10 Correct 14 ms 15116 KB Output is correct
11 Correct 12 ms 15168 KB Output is correct
12 Correct 11 ms 14932 KB Output is correct
13 Correct 276 ms 105484 KB Output is correct
14 Correct 14 ms 16240 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14420 KB Output is correct
2 Correct 10 ms 14408 KB Output is correct
3 Execution timed out 1106 ms 328320 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 777 ms 141896 KB Output is correct
3 Correct 743 ms 145636 KB Output is correct
4 Execution timed out 1116 ms 352860 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Execution timed out 1104 ms 315592 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 10 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 64 ms 30732 KB Output is correct
5 Correct 36 ms 18536 KB Output is correct
6 Correct 106 ms 40268 KB Output is correct
7 Correct 52 ms 30156 KB Output is correct
8 Correct 46 ms 27560 KB Output is correct
9 Correct 140 ms 61444 KB Output is correct
10 Correct 14 ms 15116 KB Output is correct
11 Correct 12 ms 15168 KB Output is correct
12 Correct 11 ms 14932 KB Output is correct
13 Correct 276 ms 105484 KB Output is correct
14 Correct 14 ms 16240 KB Output is correct
15 Correct 16 ms 14420 KB Output is correct
16 Correct 10 ms 14408 KB Output is correct
17 Execution timed out 1106 ms 328320 KB Time limit exceeded
18 Halted 0 ms 0 KB -