Submission #1205792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205792		Aiperiii	Stranded Far From Home (BOI22_island)	C++20	40 / 100	1097 ms	54460 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];
int vis[N],a[N],ok[N],ad[N];
int sum=0;
vector <int> gr;
int n,m;
void dfs(int v){
    gr.pb(v);
    sum+=a[v];
    for(auto to : g[v]){
        if(!vis[to]){
            vis[to]=1;
            dfs(to);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin>>n>>m;
    set <int> st;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st.insert(a[i]);
    }
    vector <pair <int,int> > edg;
    while(m--){
        int u,v;
        cin>>u>>v;
        edg.pb({u,v});
    }
    for(int i=1;i<=n;i++){
        ok[i]=1;
    }
    vector <int> uni;
    for(auto x : st){
        uni.pb(x);
    }
    
    for(int j=0;j<uni.size()-1;j++){
        int x=uni[j];
        
        
        for(int i=1;i<=n;i++){
            if(a[i]==x){
                ad[i]=1;
            }
        }
        
        for(auto e : edg){
            if(ad[e.ff] && ad[e.ss]){
                g[e.ff].pb(e.ss);
                g[e.ss].pb(e.ff);
            }
        }
        
        for(int i=1;i<=n;i++){
            vis[i]=0;
        }
        for(int i=1;i<=n;i++){
            if(ad[i] && !vis[i]){
                
                sum=0;
                gr.clear();
                vis[i]=1;
                dfs(i);
                
                if(sum<uni[j+1]){
                    
                    for(auto ind : gr){
                        
                        ok[ind]=0;
                    }
                }
                
            }
        }
        
    }
    
    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: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 30 / 30
• Subtask 5: 0 / 35