oj.uz

Submission #823770

# Submission time Handle Problem Language Result Execution time Memory
823770 2023-08-13T06:14:15 Z peteza Stranded Far From Home (BOI22_island) C++14
0 / 100
 128 ms 21632 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m, a, b;
long long root;
int s[200005];
int par[200005], ans[200005];
vector<tuple<int, int, int>> e1, e2;
vector<int> adj[200005];
long long sum[200005];

int fpar(int x) {
    return x == par[x] ? x : par[x] = fpar(par[x]);
}

long long dfssum(int x) {
    sum[x] = s[x];
    for(int e:adj[x])
        sum[x] += dfssum(e);
    return sum[x];
}

void dfsans(int x, int parval = -1, bool parans = 1) {
    ans[x] = (sum[x] >= parval && parans);
    for(int e:adj[x])
        dfsans(e, s[x], ans[x]);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m; root = 1ll*n*(n+1)/2;
    for(int i=1;i<=n;i++) {
        cin >> s[i]; par[i] = i;
    }
    for(int i=1;i<=m;i++) {
        cin >> a >> b;
        e1.emplace_back(max(a, b), a, b);
    }
    sort(e1.begin(), e1.end());
    for(auto e:e1) {
        if(fpar(get<1>(e)) == fpar(get<2>(e))) continue;
        e2.emplace_back(e); par[fpar(get<1>(e))] = fpar(get<2>(e));
    }
    for(int i=1;i<=n;i++) par[i]=i;
    for(auto e:e2) {
        if(s[get<1>(e)] == get<0>(e)) {
            root -= fpar(get<2>(e)); //cout << "Neg " << fpar(get<2>(e));
            adj[fpar(get<1>(e))].emplace_back(fpar(get<2>(e)));
            par[fpar(get<2>(e))] = fpar(get<1>(e));
        } else {
            root -= fpar(get<1>(e)); //cout << "Neg " << fpar(get<1>(e));
            adj[fpar(get<2>(e))].emplace_back(fpar(get<1>(e)));
            par[fpar(get<1>(e))] = fpar(get<2>(e));
        }
    }
    dfssum(root); dfsans(root);
    for(int i=1;i<=n;i++) cout << ans[i];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 87 ms 21632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 83 ms 21600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 128 ms 18000 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -