Submission #1206230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206230		Aiperiii	Stranded Far From Home (BOI22_island)	C++20	100 / 100	164 ms	59936 KiB

island

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
const int N=2e5+5;
vector <int> g[N],gr[N];
int a[N],ok[N],p[N],sum[N];
int n,m;
int find_set(int v){
    if(p[v]==v)return v;
    return p[v]=find_set(p[v]);
}

void union_set(int u,int v){
    u=find_set(u);
    v=find_set(v);
    if(gr[u].size()<gr[v].size())swap(u,v);
    
    for(auto x : gr[v])gr[u].pb(x);
    sum[u]+=sum[v];
    p[v]=u;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin>>n>>m;
    vector <pair <int,int>> vv;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        vv.pb({a[i],i});
    }
    
    while(m--){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    sort(all(vv));
    for(int i=1;i<=n;i++){
        ok[i]=1;
        gr[i].pb(i);
        sum[i]=a[i];
        p[i]=i;
    }
    for(auto [val,v] : vv){
        //cout<<val<<" "<<v<<"\n";
        set <int> x;
        for(auto to : g[v]){
            if(a[to]<val or (a[to]==val && to<v)){
                x.insert(find_set(to));
            }
        }
        
        for(auto v : x){
            //cout<<v<<" "<<sum[v]<<"\n";
            if(sum[v]<val){
                for(auto  id : gr[v]){
                    ok[id]=0;
                }
            }
        }
        //cout<<"\n";
        int ls=v;
        for(auto v : x){
            union_set(ls,v);
            ls=v;
        }
        
    }
    for(int i=1;i<=n;i++)cout<<ok[i];
}
/*
4 4
2 2 4 3
1 2
1 3
2 3
3 4
 
4 3
4 2 2 1
1 2
3 2
4 1
 
10 9
10 9 8 7 4 4 3 2 1 1
1 2
1 3
2 4
3 5
5 7
5 8
7 9
8 10
3 6

 1110101000
 
 
   1 1 1 1      1
 2 3 4 5 10 3 2 6 3
*/

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