Submission #948191

#	Time	Username	Problem	Language	Result	Execution time	Memory
948191		amirhoseinfar1385	Stranded Far From Home (BOI22_island)	C++17	100 / 100	597 ms	68296 KiB

island

#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
vector<long long>adj[maxn];
long long all[maxn],n,m,dp[maxn],vis[maxn],mishe[maxn],mn[maxn];

struct cmp {
    bool operator() (long long a, long long b) const {
		if(all[a]==all[b]){
			return a<b;
		}
		return all[a]<all[b];
    }
};

struct dsu{
	long long par[maxn],sum[maxn],mx[maxn];
	set<long long,cmp>st[maxn];
	dsu(){
		for(long long i=0;i<maxn;i++){
			par[i]=i;
		}
	}
	long long root(long long u){
		if(u==par[u]){
			return u;
		}
		return par[u]=root(par[u]);
	}
	void con(long long u,long long v){
		long long rootu=root(u),rootv=root(v);
		if(rootu!=rootv){
			if((long long)st[rootu].size()<(long long)st[rootv].size()){
				swap(rootu,rootv);
			}
			par[rootv]=rootu;
			sum[rootu]+=sum[rootv];
			mx[rootu]=max(mx[rootu],mx[rootv]);
			for(auto x:st[rootv]){
				st[rootu].insert(x);
			}
			while((long long)st[rootu].size()>0&&mx[rootu]>=all[(*st[rootu].begin())]){
				st[rootu].erase(*st[rootu].begin());
			}
		}
	}
	long long porssum(long long u){
		long long v=root(u);
		return sum[v];
	}
	long long porsy(long long u){
		long long v=root(u);
		if((long long)st[v].size()==0){
			return -1;
		}
		return (*st[v].begin());
	}
}ds;

void vorod(){
	cin>>n>>m;
	all[0]=1e9+5;
	for(long long i=1;i<=n;i++){
		cin>>all[i];
		ds.sum[i]=all[i];
		ds.mx[i]=all[i];
	}
	for(long long i=0;i<m;i++){
		long long u,v;
		cin>>u>>v;
		//cout<<"ha "<<u<<" "<<v<<endl;
		ds.st[u].insert(v);
		ds.st[v].insert(u);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

void pre(){
	vector<pair<long long,long long>>so;
	for(long long i=1;i<=n;i++){
		so.push_back(make_pair(all[i],i));
	}
	sort(so.begin(),so.end());
	vector<long long>now;
	for(long long i=0;i<n;i++){
		if(i>0&&so[i].first!=so[i-1].first){
			for(auto x:now){
				dp[x]=ds.porssum(x);
				mn[x]=ds.porsy(x);
			}
			now.clear();
		}
		long long u=so[i].second;
		now.push_back(u);
		vis[u]=1;
		for(auto x:adj[u]){
			if(vis[x]==1){
				ds.con(x,u);
			}
		}
	}
	for(auto x:now){
		dp[x]=ds.porssum(x);
		mn[x]=ds.porsy(x);
	}
	now.clear();
}

void solve(){
	vector<pair<long long,long long>>so;
	for(long long i=1;i<=n;i++){
		so.push_back(make_pair(all[i],i));
	}
	sort(so.begin(),so.end());
	for(long long i=n-1;i>=0;i--){
		long long u=so[i].second;
		//cout<<u<<" "<<dp[u]<<" "<<mn[u]<<endl;
		if(all[u]==so.back().first){
			mishe[u]=1;
		}
		if(mn[u]==-1||mishe[mn[u]]==0||dp[u]<all[mn[u]]){
			mishe[u]|=0;
		}else{
			mishe[u]|=1;
		}
	}
	for(long long i=1;i<=n;i++){
		cout<<mishe[i];
	}
	cout<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
}

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