Submission #722900

#	Time	Username	Problem	Language	Result	Execution time	Memory
722900		Mardonbekhazratov	Stranded Far From Home (BOI22_island)	C++17	0 / 100	1091 ms	13824 KiB

island

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>v;
vector<int>a,res,dp;
vector<bool>vis;

bool cmp(int c,int b){return a[c]<a[b];}

bool dfs(int x,int y){
	vis[x]=true;
	if(dp[y]>=dp[x]) dp[y]+=dp[x];
	else return false;
	for(int z:v[x]){
		//cout<<z<<endl;
		if(!vis[z]) return dfs(z,y);
	}
	return true;
}

int main(){
	int n,m;cin>>n>>m;
	a.resize(n);res.assign(n,0);
	v.resize(n);dp.resize(n);
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<m;i++){
		int a,b;cin>>a>>b;--a,--b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i=0;i<n;i++) sort(v[i].begin(),v[i].end(),cmp);
	for(int i=0;i<n;i++){
		vis.assign(n,false);
		for(int i=0;i<n;i++) dp[i]=a[i];
		for(int z:v[i]){
			if(!vis[z]) if(!dfs(z,i)) break;
		}
		bool b=true;
		for(int j=0;j<n;j++){
			if(dp[i]>=dp[j]) continue;
			b=false;
			break;
		}cout<<(b?1:0);
	}
}

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