Submission #975047

#	Time	Username	Problem	Language	Result	Execution time	Memory
975047		vjudge1	Stranded Far From Home (BOI22_island)	C++17	100 / 100	100 ms	12700 KiB

island

#include<bits/stdc++.h>
using namespace std;
const int NN=2e5+1;
long long node[NN],sum[NN];
int par[NN];
bitset<NN> ans;
int fp(int i){
    if(i==par[i]) return i;
    int p=fp(par[i]);
    if(!ans[par[i]]) ans[i]=ans[par[i]];
    par[i]=p;
    return p;
}
struct edl
{
    int a,b;
    bool operator < (const edl &rhs) const{
        return max(node[a],node[b])<max(node[rhs.a],node[rhs.b]);
    }
};
vector<edl> v;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m,a,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {cin>>node[i],par[i]=i; sum[i]=node[i];}
    while(m--){
        cin>>a>>b;
        v.push_back({a,b});
    }
    sort(v.begin(),v.end());
    ans.set();
    for(auto i:v){
        int p1=fp(i.a);
        int p2=fp(i.b);
        if(p1==p2) continue;
        // cout<<p1<<" "<<p2<<"\n";
        if(node[p1]<node[p2]) swap(p1,p2);
        if(node[p1]>sum[p2]) ans[p2]=0;
        par[p2]=p1;
        sum[p1]+=sum[p2];
    }
    for(int i=1;i<=n;i++){
        fp(i);
        cout<<ans[i];
    }
}

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