Submission #823770

#	Time	Username	Problem	Language	Result	Execution time	Memory
823770		peteza	Stranded Far From Home (BOI22_island)	C++14	0 / 100	128 ms	21632 KiB

island

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35