Submission #710991

#	Time	Username	Problem	Language	Result	Execution time	Memory
710991		ld_minh4354	Stranded Far From Home (BOI22_island)	C++17	40 / 100	1067 ms	30996 KiB

island

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define debug(x) cout<<#x<<": "<<x<<"\n"

int n,m,s[200005],ans[200005],cur_s;
vector<int> adj[200005],nodes;
bool vis[200005];

void dfs(int x,int max_s)
{
	if (vis[x]) return;
	vis[x]=true;
	
	cur_s += s[x];
	nodes.pb(x);
	
	for (auto y:adj[x]) dfs(y,max_s);
}

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.000","r",stdin);
//	freopen("output.000","w",stdout);
//	srand((unsigned)time(NULL));
//	rand()
	
	int i,j,pos,next_sval;
	pair<int,int> p[200005],ed[200005];
	priority_queue<pair<int,int>> q;
	set<int> sval;
	
	cin>>n>>m;
	for (i=1;i<n+1;i++) cin>>s[i];
	for (i=1;i<m+1;i++) cin>>ed[i].fi>>ed[i].se;
	
	for (i=1;i<n+1;i++) sval.insert(s[i]);
	sval.insert(1e18);
	
	for (i=1;i<n+1;i++) ans[i]=1;
	for (auto x:sval) if (x!=1e18)
	{
		for (i=1;i<n+1;i++) while (adj[i].size()>0) adj[i].pop_back();
		
		for (i=1;i<m+1;i++) if (s[ed[i].fi]<=x and s[ed[i].se]<=x)
		{
			adj[ed[i].fi].pb(ed[i].se);
			adj[ed[i].se].pb(ed[i].fi);
		}
		
		for (i=1;i<n+1;i++) vis[i]=false;
		next_sval=*sval.upper_bound(x);
		
		for (i=1;i<n+1;i++) if (!vis[i] and s[i]<=x)
		{
			cur_s=0;
			while (nodes.size()>0) nodes.pop_back();
			
			dfs(i,x);
//			cout<<x<<" "<<i<<" "<<cur_s<<"\n";
			
			if (cur_s<next_sval and next_sval!=1e18) for (auto y:nodes) ans[y]=0;
		}
		
//		for (i=1;i<n+1;i++) cout<<ans[i];
//		cout<<"\n";
	}
	
	for (i=1;i<n+1;i++) cout<<ans[i];	
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:33:8: warning: unused variable 'j' [-Wunused-variable]
   33 |  int i,j,pos,next_sval;
      |        ^
island.cpp:33:10: warning: unused variable 'pos' [-Wunused-variable]
   33 |  int i,j,pos,next_sval;
      |          ^~~
island.cpp:34:16: warning: unused variable 'p' [-Wunused-variable]
   34 |  pair<int,int> p[200005],ed[200005];
      |                ^

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