Submission #1272885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272885		vulestamenkovic	Stranded Far From Home (BOI22_island)	C++20	100 / 100	475 ms	184904 KiB

island

#include <bits/stdc++.h>
#define MAXN (int)2e5+5
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
using namespace std;
int a[MAXN];
vector<int>g[MAXN];
int p[MAXN],s[MAXN],r[MAXN],l[MAXN],o[MAXN],e[MAXN],b[MAXN],t[MAXN],dp[MAXN];
queue<int>q[MAXN];
int find(int x){
    if(x==p[x]){
        return x;
    }
    return p[x]=find(p[x]);
}void unite(int u,int v){
    u=find(u);
    v=find(v);
    if(u==v){return;}
    if(r[u]<r[v]){
        swap(u,v);
    }
    r[u]+=r[v];
    s[u]+=s[v];
    p[v]=u;
}
void solve(){
    int n,m;cin>>n>>m;
    map<int,vector<int>>v;
    vector<pii>v2;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        p[i]=i;r[i]=1;s[i]=a[i];o[i]=e[i]=0;
        v[a[i]].push_back(i);
        v2.emplace_back(a[i],i);
    }for(int i=0;i<m;i++){
        int u,v;cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(auto&x:v){
        for(int&y:x.se){
            for(int&l:g[y]){
            	if(a[l]>a[y]){continue;}
            	int u=find(l);
            	while(!q[u].empty()&&a[q[u].front()]<x.fi){
            		e[q[u].front()]=y;
            		q[u].pop();
            	}
                unite(y,l);
            }
        }
        for(int&y:x.se){
        	t[y]=s[find(y)];
        	q[find(y)].push(y);
        }
    }
    dp[0]=1;
    a[0]=-1;
    sort(v2.begin(),v2.end());
    for(int j=n-1;j>=0;j--){
    	int i=v2[j].se;
    	dp[i]=(a[e[i]]<=t[i]?dp[e[i]]:0);
    }for(int i=1;i<=n;i++){
    	cout<<dp[i];
    }cout<<'\n';
}
int32_t main(){
    int32_t T=1;//cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

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