Submission #828475

#	Time	Username	Problem	Language	Result	Execution time	Memory
828475		Pacybwoah	Stranded Far From Home (BOI22_island)	C++17	100 / 100	359 ms	41776 KiB

island

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#define ll long long
using namespace std;
vector<int> dsu,sz,ans;
vector<ll> sum;
vector<set<int> > nodes;
void build(int n){
    dsu.resize(n+1);
    sz.resize(n+1);
    for(int i=1;i<=n;i++) dsu[i]=i,sz[i]=1,nodes[i].insert(i);
}
int query(int x){
    if(dsu[x]==x) return x;
    return query(dsu[x]);
}
void unite(int a,int b,int ori){
    a=query(a),b=query(b);
    if(a==b) return;
    if(ori>sum[b]){
        for(auto x:nodes[b]){
                    ans[x]=0;
                }
                nodes[b].clear();
    }
    if(sz[a]<sz[b]) swap(a,b);
    dsu[b]=a;
    sz[a]+=sz[b];
    sum[a]+=sum[b];
    for(auto x:nodes[b]) if(ans[x]==-1) nodes[a].insert(x);
    nodes[b].clear();
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector<vector<int> > graph;
    ans.resize(n+1,-1);
    nodes.resize(n+1);
    graph.resize(n+1);
    sum.resize(n+1);
    vector<pair<ll,int> > val(n);
    for(int i=1;i<=n;i++) cin>>val[i-1].first,val[i-1].second=i,sum[i]=val[i-1].first;
    int a,b;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        if(val[a-1]<val[b-1]) graph[b].push_back(a);
        else graph[a].push_back(b);
    }
    sort(val.begin(),val.end());
    build(n);
    for(int i=0;i<n;){
        int now=i;
        while(now<n&&val[i].first==val[now].first){
            for(auto x:graph[val[now].second]){
                unite(val[now].second,x,val[now].first);
            }
            now++;
        }
        if(now==n) break;
        for(int j=i;j<now;j++){
            int mum=query(val[j].second);
            //cout<<val[j].second<<" "<<sum[mum]<<"\n";
            if(sum[mum]<val[now].first){
                for(auto x:nodes[mum]){
                    ans[x]=0;
                }
                nodes[mum].clear();
            }
        }
        i=now;
    }
    for(int i=1;i<=n;i++){
        if(ans[i]==-1) cout<<1;
        else cout<<0;
    }
}

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