Submission #975032

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

island

#include<bits/stdc++.h>
using namespace std;
const int NN=2e5+1;
long long node[NN];
int par[NN];
bitset<NN> ans;
int fp(int i){
    if(i==par[i]) return i;
    int p=fp(par[i]);
    if(ans[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;
    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]>node[p2]) ans[p2]=0;
        par[p2]=p1;
        node[p1]+=node[p2];
    }
    for(int i=1;i<=n;i++){
        fp(i);
        cout<<ans[i];
    }
}

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