Submission #1098931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098931		origabai	Stranded Far From Home (BOI22_island)	C++14	100 / 100	142 ms	48308 KiB

island

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> par;
vector<int> ans;

int cmp(int v){
    if (par[v]==v) return v;
    return par[v] = cmp(par[v]);
}

void dfs1(vector<int> tree[], ll sum[], ll s[], int v){
    sum[v] = s[v];
    for (int u : tree[v]){
        dfs1(tree,sum,s,u);
        sum[v] += sum[u];
    }
}

void dfs2(vector<int> tree[], ll sum[], ll s[], int v){
    ans[v]=1;
    for (int u : tree[v]){
        if (sum[u] >= s[v]){
            dfs2(tree,sum,s,u);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    ll s[n];
    for (int i=0;i<n;i++){
        cin >> s[i];
    }
    vector<int> nei[n],tree[n];
    for (int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        nei[a].push_back(b);
        nei[b].push_back(a);
    }
    par.resize(n);
    iota(par.begin(),par.end(),0);
    vector<int> ord(n);
    iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int l, int r){return s[l] < s[r];});
    bool vis[n]={0};
    for (int v : ord){
        vis[v]=1;
        for (int u : nei[v]){
            if (vis[u]){
                u = cmp(u);
                if (u==v)continue;
                tree[v].push_back(u);
                par[u] = v;
            }
        }
    }
    ans.resize(n);
    ll sum[n];
    dfs1(tree,sum,s,ord.back());
    dfs2(tree,sum,s,ord.back());
    for (int i=0;i<n;i++){
        cout<<ans[i];
    }
    cout<<"\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35