Submission #828253

#	Time	Username	Problem	Language	Result	Execution time	Memory
828253		Pacybwoah	Stranded Far From Home (BOI22_island)	C++17	0 / 100	323 ms	40072 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){
    a=query(a),b=query(b);
    if(a==b) return;
    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;i++){
        for(auto x:graph[val[i].second]){
            unite(x,val[i].second);
        }
        int mum=query(val[i].second);
        if(i!=n-1&&sum[mum]<val[i+1].first){
            for(auto x:nodes[mum]){
                //cout<<val[i].second<<" "<<x<<"\n";
                ans[x]=0;
            }
            nodes[mum].clear();
        }
    }
    for(int i=1;i<=n;i++){
        if(ans[i]==-1) cout<<1;
        else cout<<0;
    }
}

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