Submission #823772

#	Time	Username	Problem	Language	Result	Execution time	Memory
823772		peteza	Stranded Far From Home (BOI22_island)	C++14	100 / 100	134 ms	29464 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(s[a], s[b]), a, b);
    }
    sort(e1.begin(), e1.end());
    for(auto e:e1) {
        //cout<<get<0>(e);
        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)) {
            //cout << get<1>(e) << ' ' << get<2>(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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35